22.174 0-65 УДК 519 Оре О. Теория графов.—2-е пзл.—М.: Наука, Главная редакция фи- зико-математической литературы, 1980, 336 с. Первые пять глав посвящены наглядному материалу и содержат ос- новные понятия и свойства графов. В шестой главе даются основы тео- рии вполне упорядоченных можеств, которая используется в дальней- шем для строго абстрактного рассмотрения бесконечных графов. Осо- бенно подробно, в главе 7, излагается вопрос о паросочетаниях; естественным ее продолжением является глава 12. В главах 8—11 рас- сматриваются ориентированные графы, и затем на языке ориентирован- ных графов изучаются частично упорядоченные множества. Последние три, очень интересные, главы (13—15) снова имеют дело с более на- глядным материалом. Книга дает достаточно полное представление о направлениях иссле' дований в теории графов; приводятся упражнения и нерешенные задачи; сделана попытка ввести систематическую терминологию. Напи- сана книга ясным и достаточно доступным математическим языком. Она интересна ч нужна специалистам-математикам, инженерам, зани- мающимся прикладными задачами, и студентам старших курсов уни- верситетов и технических вузов. Библ.— свыше 200 назв. Плл. 88. Ойстин Оре • ТЕОРИЯ ГРАФОВ М., 1980 г., 336 стр. с илл. Редактор И. М. Овчинникова Технический редактор Е. В. Морозова Корректор Н, В. Румянцева ИВ М 11700 Сдано в набор 12.12.79. Подписано к печати 110G.80. Бумага 84х108'Лг. run. JSi 1. Обыкновенная гарнитура. Высокая печать. Услоан. печ. л, 17,В4. Уч.-изд. л. 17,18. Тираж 29000 экз. Заказ №791. Цена книги 1 р. 50 к. Издательство «Паука» Главная редакция ((пппко-математнческой литературы 117071, Москва, В-71, Ленинский проспект, 15 4-я типография издательства «Наука», 630077, Новосибирск, 77, Станиславского, 25. О ж03 ~ 086 48-80 1702070000 053 (02)-80 ОГЛАВЛЕНИЕ От редактора русского перевода . . . . . Предисловие . .......... Глава 1. ОСНОВНЫЕ ПОНЯТИЯ ...".. 1.1. Определения . ........ 1.2. Локальные степени . ...... 1.3. Части и подграфы ....... 1.4. Бинарные отношения . . . . . . 1.5. Матрицы смежности и инцидентности Глава 2. СВЯЗНОСТЬ ......... 2.1. Маршруты, цепи и просгые цепи 2.2. Связные компоненты ....... 2.3. Взаимно однозначные отображения 2.4. Расстояния . ........ 2.5. Протяженность . ....... 2.6. Матрицы и цепи. Произведение графов 2.7. Головоломки . ........ Глава 3. ЗАДАЧИ О ЦЕПЯХ ....... 3.1. Эйлеровы цепи . ....... 3.2. Эйлеровы цепи в бесконечных графах 3.3. О лабиринтах . ....... 3.4. Гамильтоновы циклы . . . . . . Глава. 4. ДЕРЕВЬЯ . ........ 4.1. Свойства деревьев . ...... 4.2. Центры в деревьях ....... 4.3. Циклический ранг (цикломатичсское чпс.к^ 4.4. Однозначные отображения . .... 4.5. Произвольно вычерчиваемые графы , Глава 5. ЛИСТЫ II БЛОКИ ....... 5.1. Соединяющие ребра и вершины 5.2. Листы . ......,,.. 5.3. Гомоморфные образы графа ..... 5.4. Блоки . .......... 5.5. Максимальные простые циклы , , , . Глава 6. АКСИОМА ВЫБОРА . ....... 6.1. Полная упорядоченность , ...... 6.2. Принципы максимальности ....... 6.3. Суммируемые по цепи свойства ..... 6.4. Максимальные графы исключения ..... 6.5. Максимальные деревья . ....... 6.6. Соотношения между максимальными графами Глава 7, ТЕОРЕМЫ О ПАРОСОЧЕТАННЯХ .... 7.1. Двудольные графы ........> 7.2. Дсфпцпты . ........... 7.3. Теоремы о паросочетанпях ....... 7.4. Взаимные паросочетания . ...... 7.5. Паросочетания в графах частного вида . . . 7.6. Двудольные графы с положительными дсфпынтами 7.7. Применения к матрицам ....... 7.8. Чередующиеся цепи и максимальные паросочетания 7.9. Разделяющие множества ,,..... 7.10. Совместные паросочетания .,..,.. Глава 8. ОРИЕНТИРОВАННЫЕ ГРАФЫ ..... 8.1. Отношение включения и достижимые множества й.2. Теорема о гомоморфизме ....... 8.3. Транзитивные графы п погружения в отношения упорядочения ........... 8.4. Базисные графы .......... 8.5. Чередующиеся цепи ......... 8.6. Суграфы первой степени в графе ..... Глава 9. АЦИКЛИЧЕСКИЕ ГРАФЫ ....... 9.1. Базисные графы .......... 9.2. Деформации цепей . ........ 9.3. Графы воспроизведения ........ Глава 10. ЧАСТИЧНАЯ УПОРЯДОЧЕННОСТЬ .... 10.1. Графы частичных упорядочений ..... 10.2. Представления в виде сумм упорядоченных множеств ............ 10.3. Структуры и структурные операции. Отношения замыкания . ........,, 10.4. Размерность в частичном упорядочении . . . Глава 11. БИНАРНЫЕ ОТНОШЕНИЯ И СООТВЕТСТВИЯ ГАЛУА . ........... 11.1. Соответствия Галуа ......... 11.2. Связи Галуа для бинарных отношений . . , 11.3. Отношения чередующегося произведения , . 11.4. Отношения Феррсрса .. .,..>• Глава 12. СВЯЗЫВАЮЩИЕ ЦЕПИ ....... 12.1. Теорема о секущих цепях ....... 12.2. Вершинное разделение .,.,.... 12.3. Реберное разделение , ....... 12.4. Дефицит . . .......... Глава 13. ДОМИНИРУЮЩИЕ МНОЖЕСТВА, ПОКРЫВАЮ- ЩИЕ МНОЖЕСТВА И НЕЗАВИСИМЫЕ МНОЖЕСТВА 13.1. Доминирующие множества ....... 13.2. Покрывающие множества и покрывающие суграфы 13.3. Независимые множества ....... 13.4. Теорема Турана .......... 13.5. Теорема Рамсея .......... 13.6. Одна задача из теории информации .... Глава 14. ХРОМАТИЧЕСКИЕ ГРАФЫ ...... 14.1. Хроматическое число ........ 14.2. Суммы хроматических графов .... . 14.3. Критические графы .........: 14.4. Полиномы раскрашивании ....... Глава 15. ГРУППЫ И ГРАФЫ ........ 15.1. Группы автоморфизмов ......... 15.2. Цветные графы Кэля для групп ...... 15.3. Графы с заданными группами ...... 15.4. Реберные отображении ......... Литература ............... Именной указатель . ........... Предметный указатель ............ ЛИТЕРАТУРА Глава 1 С. В е г g e, Theorie des graphes et ses applications. Paris, 1958. Есть русский перевод: Б е р ж К., Теория графов и ее применения, ИЛ, М., 1962. D. К б n i g, Theorie der endlichen und unendlichen Graplien. Leipzig, 1936. A. Sainte-LaguS, Les reseaux (ou graphes). Мёшог. Sci. Math., v. 18, 1926. Многие сборники математических головоломок содержат за- дачи, которые можно сформулировать в терминах графов. Мы ука- жем здесь лишь следующие: YV. Rouse-Ball, Mathematical recreations and problems. London, 1892. Numerous editions. E. Lucas, Recreations mathematiques. 3 v., Paris, 1882—1894. Есть русский перевод: Люкс Е. Л., Математические развлечения, СПБ. 1883. Глава 2 2.7. D. W. Crow e, The re-dimensional cube and the tower of Hanoi. Amer. Math. Monthly, v. 63 (1956), pp. 29—30. Глава 3 3.1 L. E u 1 е г, Solutio problematis ad geometriam situs pertinentis. Com- mentarii Academiae Petropolitanae, v. 8 (1736), pp. 128—140. N. G. d e В г u i j n, A combinatorial problem. Nederl. Akad. We- tensch. Proc., v. 49 (1946), pp. 758—764. Van Aardenne-Ehrenfest and N. G. d e В г u I j n, Circuits and trees in oriented graphs. Simon Stevin, v, 28 (1951), pp.203—217. 3.2 Р. Е г d о s, Т. G г и n w а 1 d and Е. W e i s z f e 1 d, Uber Eulerscha Linien unendlicher Graphen, Mat, Fiz. Lapok, v. 43 (1936), pp. 129-140, 314 Г. E r d о s, Т. G r U n w a I d and E. V а г & о п у 1, ОЬег Euler-Linien unciidlicher Graplien. J. Math. Phys. Massachussets Inst. of Technology, v. 17 (1938), pp. 59—75. E. Vazsonyi, Uber Gitterpunkte des mehrdimensionalen Baumes. Acta Litt. Sci. Szeged, v. 9 (1939), pp. 163—173. G. R i n g e 1, Uber drei kombinatorische Probleme аш n-dimensiona- len Wiirfel und Wflrfelgitter. Abh. Math. Sem. I'niv. Hamburg, v. 20 (1955), pp. 10—19, 8.3 С. W i e n e г, L'ber eine Aufgabe aus der Geometria situs. Math. Ann., v.6 (1873), pp. 29—30. О. О r e. An Excursion into labyrinths. Mathematics Teacher, v. 52 (1959). pp.367—370. " Beckman, С. В. McGuire and С. В. Winsten, Studies in the economics of transportation. New Haven, Yalo University Press, 1956. L. R. Ford, Network flow theory. Rand Corp. PubL P-23 (1956). Добавление к русскому переводу: Форд Л. Р. и Фалкерсон Д. Р., Потоки в сетях, «Мир», NL, 1906. 8.4 D. J. N e w m a n, A problem in graph theory. Amer. Math. Monthly, v. 6,"» (1958), p. 611. ' — ' 0. Ore, Note on Hamilton circuits. Amer. Math. Monthly, v. 67 (1960), p. 55. W. T. Tutte, On Hamilton circuits. J. London Math. Soc., v. 21 (1946), pp. 98—101. F. Sup nick, Extreme Hamilton lines. Ann. of Math. (2), v. 66 (1957), pp. 179—201. F. Fitting, Doppellsymmelrische Rosselsprunge auf Quadraten von ungeraden Felderzahl ohne Mittelfeld. Jber. Deutsch. Math. Ve- rein, v. 46 (1936), Abt. 1, pp. 38—43. G. I. M G. R. Dantzig, R. Fulkerson and S. J о b n s о n, Solution of a large-scale travelling-salesman problem. Journal Operational Re- search Soc. of Amer., v. 2 (1954), pp. 393—410. Heller, Tlie travelling-salesman problem. George Washington Univ. Logistics Research Project, 1954. M. Flood, On the travelling salesman's problem. Journal Ope- rational Research Soc. of Amer., v. 4 (1956), pp. 61—75. T. S. M о t z k i n and E. G. S t г a u s, Some combinatorial extremum problems. Proc. Amer. Math. Soc., v. 7 (1956), pp. 1014—1021. Dantzig, R. Fulkerson and S. J о h n s о n, On a linear programming combinatorial approach to the travelling-salesman problem. Journal Operational Research Soc. of Amer., v. 7 (1959), pp. 58—66. Bellman, On a routing problem. Quart. Appl. Math., v, 16 (1958), pp. 87—90. Саvlev, A theorem on trees. Quarterly Journal of Pure and Appl. Math., v. 23 (1889), pp. 376—378. Priifer, Neuer Beweis eines Satzes uber Permutationen. Archiv der Math. und Phys. (3), v. 27 (1918), pp. 142—144. Dziоbek, Eine Fonnel der Substiliitionstheorie. Sitzungsberlchte der Berliner Math. Gcsellschaft, v. 16 (1947), pp. 64—67. Воl, Uber eine kombinatorische Frage. Abh. Matli. Seminar der Hansischen Univ., v. 12 (1938), pp. 242—245. II. Neville, The codifying of tree-structure. Proc. Cambridge Philos. Soc., v. 49 (1953), pp. 381—385. Bott and J. P. Mayberry, Matrices and trees. Также T. M. Whitin, An economic application of «Matrices and Trees». Опубликованы в сП. О. M о r g e n s t e r n: Economic Activity Analysis, New York, John Wiley and Sons, 195'!. Vitalhi, Picerche sulla teoria dei reticoli. Giorn. Mat. Battaglini (5), v. 4 (84) (1956), pp. 93—121. Andreоli, Preliminari topologici su gli alberi. Giorn. Mat. Baltaglini (5), v. 2 (82) (1954), pp. 237—266. I. Kellv, A congruence theorem for trees. Pacific J. Math., v. 7 (1957), pp. 961—968. Poly a, Kombinatorische Anzahlbeslimmnngen fur Gruppen, Craphpn und chemische Verbindungon. Acta Math., v. 68 (1937), pp. 145—254. Riоrdan, An introduction to combinatorial analysis. John Wiley and Sons, New York, 1958. Есть русский перевод: Риордан Дж., Введение в комбинаторный анализ, ИЛ, M., 1963. Воruvka. On a minimal problem. Prace Moraske Pridovedecke Spolecnosii, v. 3 (1926). Jarnik and M. Kossler, Sur les graphes minima contenant n points donnes. Casopis Mat. Fys., v. 63 (1934), pp. 223—235. Choquet. Etude de corlains reseaux de routes. C. B. Acad. Sci. Paris, v. 206 (1938), pp. 310-313. B. Kruskal, On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Amer. Math. Soc., v. 7 (1956), pp. 48—50. D. Blanusa, Uber die Anzahl der Bedingnngsgleichungen bcliebigen geodatischcn Netzcn. Z. Vermessungswesen, v. 73 (1944), pp. 54-62. Ore, Graphs and correspondences. Festschrift Andreas Speiser Zurich (1945), pp. 184— W. Ore, Incidence matchings in graphs. Journ. (1961), pp. 123—127. de Malh., v. 40 Ore, Incidence matchings in graphs. Journ. (1961), pp. 123—127. de Malh., v. 40 316 О. О г e, A problem regarding the (racing of graphs. Elem. Math., v. 6 (1951), pp. 49—53. F. A. F. В а Ы e г, Ober eino speziclle Klasse Eiilor'schor Graphen Com- ment. Malh., Helv., v. 27 (1953), pp. 81—100. На гаг у. On arbitrarily traceable graphs and directed graplis. Scripta Math., v. 23 (1957), pp. 37—41. Дополнительные работы по теории деревьев К о t z i g, The significance of the skeleton of a graph for the con- struction of composition bases of some subgraphs. Mat. Fyz. Ca- sopis Slovensk. Akad. Vied., v. 6 (1956), pp. 68—77. W. T. T u 11 e, A ring in grapli theory. Proc. Cambridge Philos. Soc., v. 43 (1947), pp. 26—40. J. S. R. Chisholm, The 5-malrix for neutral PS — PV meson- nucleon interaction. Phil. Mag. (8), v. 1 (1956), pp. 338—344. W. H. В urge, Sorting, trees and measures of order. Information and Control, v. 1 (1958), pp. 181—197. Глава 5 5.1 S. Maclane, Some unique separation theorems for graphs. Amcr. J. Math., v. 57 (1935), pp. 805—820. R.E. Nettleton, K. Goldberg and M. S. Green. Dense sub- graphs and connectivity. Canad. J. Math,, v. 11 (1959), p. 262—268. 5.4 II. Whitncy, Non-separable and planar graphs. Trans. Amer. Malh. F. К. P. Soc., v. 34 (1932), pp. 339—362. 17 На гаг у, An elementary theorem on graphs. Amer. Malli. Monthly, v. 66 (1959), pp. 405—407. Husimi, Note on Mayors' theory of cluster integrals Journ. Chem. Phys., v. 18 (1950), pp. 682—684. И а г а г у and G. E. U h I e n b e с k, On the number of IIusimi trees. Proc. Nat. Acad. Sci. U. S. A., v. 39 (1953), pp. 315—322. F. II а г а г у and R. Z. Norman, The dissimilarity characteristic of Husimi trees. Ann. of Malh. (2), v. 59 (1953), pp. 134—141. G. A. D i г а с, Some theorems on abstract Math. Soc. (3), v. 2 (1952), pp. 69—81. Р. E г d б s and T. G а 11 a i, On maximal graphs, Acta Math. Acad. Sci. Hungar., v. graphs, Proc. London paths and circuits of 10 (1959), pp. 337-350. ЛИТЕРАТУРА 317 Глава 6 6.4 0. 0 r e and T. S. M о t z k i n, Subsets and subgraphs with maximal properties. Proc. Amer. Math. Soc., v. 10 (1959), pp. 965—969. Глава 7 7.1 R. R a d о, Axiomatic treatment of rank in infinite sets. Canad J. Math., v. 1 (1949), pp. 337—343. \V. H. G о 11 s с h a 1 k, Choice functions and Tychonoff's theorem. Proc. Amer. Math. Soc., v. 2 (1951), p. 172. 7.3 0. Ore, Graphs and matching theorems. Duke Math. J., v. 22 (1955), pp. 625—639. P. Hal 1, On representatives of subsets. T. London Math. Soc,, v. 10 (1935), pp. 26-30. M. Hall, District representatives of subsets. Bull. Amer. Math. Soc., v. 54 (1948), p. 922—926. 7.4 N. G. de Bruijn, Gemeeiischapelijke represenlanlensystemen vari twee klassenindeelingen van een vcrsameling. Nieuw Archicv voor Wiskunde (2), v. 22 (1943), pp. 48—52. G r u n w a 1 d, Uber einen mengenthooretischen Satz. Math. Fiz. Lapok, v. 44 (1937), pp. 51-53. M II all, An algorithm for distinct representatives. Amer. Math. Monthly, v. 63 (1956), pp. 716—717. R. II a 1m os and II. E. Vaughan, The marriage problem. Amer. J. Math., v. 72 (1950), pp. 214—215. II e n k i n, Some interconnections between modern algebra and mathematical logic Trans. Amer. Math. Soc., v. 74 (1953), pp. 410—427. P. J. H i g g i n s, Disjoint transversals of subsets. Canad. J. Math., v.11 (1959), pp. 280—285. J. H о f f m a n and H. W. K u h n, Systems of distinct represen- tatives and linear programming. Amer. Math. Monthly, v. 63 (1956), pp. 455—460. A. J. H о f f m a n and H. W. K u h n, On systems of distinct repre- sentatives. Annals of Math. Studies, No. 38 (1956). Есть русский перевод: Гофман А. Д эк., К у н Г. У., О системах различ- ных представителей. В сб. «Линейные неравенства и сменжые вопросы», ИЛ, M., 1959, 302—310. G. W. Kreweras, Extension d'un theoreme sur les repartitions en classes. C. R. Acad. Sci. Paris, v. 222 (1946), pp. 431—432. M a a k, Ein Problem der Kombinatorik in seiner Formulierung von H. WeyL Math.-Phys. Semestcrber. Gottingen, v. 22 (1952), pp. 251—256. 318 ЛИТЕРАТУРА II. В. Mann and 11. J. R у s e г, Systems of distinct representatives. Amer. Math. Monthly, v. 60 (1953), pp. 397—401. U.S. Mendelsohn and A. L. D ч 1 in a g e. Some generalizations of the problem of distinct represenlalives. Canad. J. Math., v. 10 (1958), pp. 230—241. U.S. Mendelsohn and A. L. D 111 m a g e. Coverings of bipartite graphs. Canad. J. Math., v. 10 (1958), pp. 517—534. R. R a d о, Factorization of even graplis. Quart. J. Math., Oxford, v. 20 (1949), pp. 95—104. В. Ill м v т к о в п ч. Об одпои комбинаторной теореме теории мно- жеств. Матем сб., 6 (48). 1 (1939), 139—146. В. L. van der Waerden, Ein Satz iiber Klusseneinlcilungpn von endliclien Mungcn. Hamburger Abh., v. 5 (1927), pp. 185—187. II. \V e у 1, Almost periodic invariant vector sets in a metric vector space. Amcr. J. Math., v. 71 (1949), pp. 178—20."). 7.5 G. Scorza, A proposilo di nn leoroma del Chapman. Boll. Un. Mat. Ital., v. 6 (1927), pp. 1—6. II. W. С li a p rn ;i n, A note on the elementary theory of groups of' finite order. Messenger of Math., v. 42 '(1913), pp. 132—134; v. 43, р. 85. G. A. Miller, On a inelliod due to Galois. Quart. J. Math., v. 41 (1910), pp. 382-384. S. S li ii, Он the common representative system of residue classes of infinite groups. J. London Math. Soc., v. 16 (1941), pp. 101—104. 0. Ore, On cospl representatives in groups. Proc. Amer. Math. Soc., v. 9 (1958). pp. 665—670. 0. Ore, Conditions for subgraphs of directed graplis. J. Math. Piires Appl., 37 (1958), pp. 321—328. 7.7 A. L. D u I m age and N. S. M e n d с I s о li n, The term and sto- chastic rank of a matrix. Canad. J. Ma(li..v. 11 (1959), pp. 269—27;). M. II а 11, An existence theorem for Latin i>qiiarcs. Bull. Amcr. Math. Soc., v. 51 (1945), pp. 387—388. II. J. В у so г, A combinatorial theorem with an application to Latin .rectangles. Proc. Amer. Math. Soc., v. 2 (1951), pp. 550—552. II. J. Ryser, The term rank of a matrix. Canad. J. Math., v. 10 (1958), pp. 57—65. M. Marc ws, Some properties and applications of doubly stochastic matrices. Araer. Math Monthly., v. 67 (1960), pp. 215—221. J. Singer, A class of groups associated with Latin squares. Amer. Math. Monthly, v. 67 (1960), pp. 235—240. 7.9 D. К о nig, Graphcn und Malrizes. Mat. Fiz, Lapok., v. 38 (1931), pp. 116-119. ППТТТАТУРА 819 D. Konig, U Ь e r tronnende Knotenpunkle in Graphen. Acta Litt. ac. Seient. Szeged., v. 6 (1933), pp. 155—179. D. Konig and S. V a 1 k 6. Uber Mehrdeutige Abbildungen von Mengen. Math. Ann., v. 95 (1926), pp. 135—138. R. Z. Norman and M. 0. R a b i n, An algorithm for a minimum cover of a graph. Proc. Amer. Math. Soc., v. 10 (1959), pp. 315—319. С. В e г g e, Two theorems in graph theory. Proc. Nat. Acad. Sci. U. S. A., v. 43 (1957), p. 842-844. 7.10 P. J. H i g g i n s, Disjoint transversals of subsets. Canad. J. Math., v. 11 (1959), pp. 280—285. H. J. Ryser, Combinatorial properties of matrices of zeros and ones. Canad. J. Math., v. 9 (1957), pp. 371—377. D. Gale, A theorem on flows in networks. Pacific J. Math., v. 7 (1957), pp. 1073—1082. Глава 8 6.1 H. E. R о b b i n з, A theorein on graphs with an application to a problem of traffic control. Amer. Math. Monthly, v. 46 (1939), pp. 281—283. L. E g у e d, Uber die wohlgerichteten unendlichen Graphen. Mat. Fiz Lapok., v. 48 (1941), pp. 505—509. L. B e d e i, Ein kombinatorischer Salz. Acta. Litt. Szeged, v. 7 (1934), pp.39—43. M. F r i e d 1 e r and J. Sedlacek, Uber Wurzelbasen von gerichle- ten Graphen. Casopis Pest Mat., v. 83 (1958), pp. 214—225. 8.2 R. D. Luce, Two decomposition theorems for a class of finite orien- ted graphs. Amer. J. Math., v. 74 (1952), pp. 701—722. R. D. Luce, Networks satisfying minimality conditions. Amer. J. Math., v. 75 (1953), pp. 825-838. К. cTulik, Zur Theorie der Graphen. Casopis Pest. Mat., v. 83, (1958), pp. 133—155. 8.4 L. R e d e i, Uber die Kantenbasen fur endliche vollstandige gerichteta Graphen. Acta. Math. Sci. Hungar., v. 5 (1954), pp. 17—25. 8.6 0. Ore, Studies on directed graphs. I, Ann. of Math., v. 63 (1956), pp. 383-406; II, v. 64 (1956), pp. 142-153. W. Т. Т ц 11 e, The 1-factors of oriented graphs. Proc. Amer. Math. ' Soc., V. 4 (1953), p. 922—931. 320 ЛИТЕРАТУРА Глава 9 9.2 0. Ore, Chains in partially ordered sets. Bull. Amer. Math. Soc., v. 49 (1943), pp. 558—566. S. M а с 1 a n e, A conjecture of Ore in partially ordered sets. Bull. Amer. Math. Soc., v. 49 (1943), pp. 567—568. M. В e n a d о, Les ensembles partiellement ordonnes et le iheoreme de raffinement de 0. Schreier. Acad. R. P. Romme Bul. Sti. Sec(. Sti. Mat. Fiz., v. 4 (1952), pp. 585—591. M. В e n a d о, Bemerkungen zu einer Arbeit von Oystein Ore. Rev. Math. Pures Appl., v. 1 (1956), pp. 5—12. M. К о 1 i b i a r, Bemerkung fiber die Kelten in teilweise geordneten Mengen. Acta Fac. Nat. Univ. Comenian, v. 3 (1958), pp. 17—22. 9.3 0. Ore, Sex in graphs. Proc. Amer. Matli. Soc., v. 11 (1960), pp. 533—539. Глава 10 10.2 В. P. D i 1 w о r t h, A decomposition theorem for partially ordered sets. Ann. of Math. (2), v. 51 (1950), pp. 161—166. G. A. M о r e i r a, Decomposition of partially ordered systems. Revis- ta Cientifica, v. 1 (1950), pp. 12—18.^ D. T. Fulkerson, Note on Dilworth's decomposition theorem for partially ordered sets. Proc. Amer. Math. Soc., v. 7 (1956), pp. 701—702. G. В. D a n t z i g and A. J. H о f f m a n, Dilworth's theorem on par- tially ordered sets. Annals of Math. Studies, No. 38 (1956), pp. 207—214. Есть русский перевод: Д а н ц и г Дяг. Б., Гоф- ман Л. Д ж., Теорема Дилворта о частично упорядоченных множествах. В сб. «Линейные неравенства и смежные вопро- сы», ИЛ, M., 1959, 311—317. G. В i r k h о f f, Lattice theory. Amer. Math. Soc. Colloquium PubL, v. 25, Rev. ed. 1948. Есть русский перевод: Б и р к г о ф Г., Теория структур, ИЛ, M., 1952. 10.4 E. Szpilrajn, Sur 1'extension de I'ordere partiel. Fund. Math, v. 16 (1930), pp. 386-389. В. D u s h n i k and E. W. Miller, Partially ordered sets. Amer. J. Math., v. 63 (1941), pp. 600—610. В. D u s h n i k, Concerning a certain set of arrangements. Proc. Amer. Math. Soc., v. 1 (1950), pp. 788—796. В. D u s h n i k and E. W. M i 11 e r, Partially ordered sets. Ашег. J. Math., v. 70 (1948), pp. 507—520. ЛИТЕРАТУРА 821 V. S e d m a k. Dimension des ensembles parliellement ordonnes asso- cies aux polygones et polyedres. Hrvatsko, Prirodoslovno Drustvo Glasnik Mat.-Piz. Astr., Ser. II, v. 7 (1952), pp. 169—182. V. S e d m a k, Quelques applications des ensembles partiellement or- donnes. C. R. Acad. Sci. Paris, v. 236 (1953), pp. 2139—2140. T. H i r a g u с h i, On the dimension of partially ordered sets. Sci. Rep. Kanazawa University, v. 1 (1951), pp. 77—94. T. U i r a g u с li i. A note on Mr. Komm's theorems. Ibid., v. 2 (1953), No. 1, pp. 1—3. T. H i r a g u с li i, On tlie dimension of orders. Ibid., v. 4 (1955), No. 1. T. H i r a g u с h i, On the ^-dimension of the product of orders. Ibid., v. 5 (1956), pp. 1—5. Г л а в а 11 11.1 О. Ore, Galois connexions. Trans. Amer. Math. Soc., v. 55 (1944), пр. 493—513. G. B i r k h о f f, Lattice- theory. 2nd od., 1948, Chapter IV. Есть рус- ский перевод: Биркгоф Г., Теория структур, ИЛ, M., 1952, гл. IV. С. J. E v e r e 11, Closure operators and Galois theory in lattices. Trans. Amer. Math. Soc., v. 55 (1944), pp. 514—525. G. Picker t, Burncrkungcn fiber Galois-Vcrbindungen. Arch. Math., v, 3 (1952), pp. 285—289. G. A u m a n n, Bemorkungen fiber Galois-Verbindungen. Bayer. Akad. Wiss. M. N. Kl. (1955), pp. 281—284. 11.3 ] R i g u e t, Relations binaires, fermetiires, correspondences do Ga- lois. Bull. Soc. Math. France, v. 76 (1948), pp. 114—155. ] R i g u e t, Oiielques proprietos des relations difonctionellcs. C. R. Acad. Sci. Paris., v. 230 (1950), pp. 1999—2000. .1 li i g u с t, Sur les ensembles reguliors de relations binaires. C. R. Acad. Sci. Paris, v. 231 (1950), pp. 936—937. M L. D u b г с i 1 - J а с о t i n, Quclques proprieles des applications iiiulliforines. C. R. Acad. Sci. Paris, v. 230 (1950), pp. 806—808. G. Y. R a i n i с h, Involution and equivalence. Michigan Math. J., v. 2 (1954), pp. 33—34. 11.4 J R i g u e t, Les relations de Ferrers. C. R. Acad. Sci. Paris, v. 232 (1951), pp. 1729—1730. P D u b r e i 1, Relations binaires et applications. C. R. Acad. Sci. Paris, v. 230 (1950), pp. 1028—1030. P. D u b г e i 1, Comportement des relations binaires dans une appli- cation multiform e. C. R. Acad. ScL Paris, v. 230 (1950), pp. 1242—1243. R. M. Thrall, A combinatorial problem. Michigan Math. J., v. I (1952), pp. 81-88, 21 о. Opt Lambek, Goursat's theorem and the Zassenhaus lemma. Canad J. Math., v. 10 (1958), pp. 45—56. 0 n о. On some properties of binary relations. Nagoya Math. J v. 12 (1957), pp. 161-170. Глава 12 ,12.2 К о n i g. Cher trennende Knotenpunkte in Graphen. Acta Lilt. Sci. Szeged, v. 6 (1933), pp. 155—179. H a j о s, Ziim Merigerschen Graphensatz. Acta. Lilt. Scl. Szeged, v. 7 (1934), pp. 44-47. Criinwald, Ein neuer Beweis eines Mengerschen Satzes. J. London Math. Soc., v. 13 (1938), pp. 188—192. A. Dirac, Connectivity theorems for graphs. Quarterly J. Math., Oxford Ser. (2), v. 3 (1952), pp. 171—174. Глава 13 13.1 S с h e i d, Some packing problems. Amer. Math. Monthly., v. 67 (1960), pp. 231-235. 13.3 N e 11 о, Lehrbuch der Combinatorik, 2. Aufl., 1927. . S i e r p i n s k i, Sur un probleme de la theorie des relations. Fund. Math., v. 28 (1937), pp. 71—74. Piccard, Solution d'un probleme de la theorie des relations. Fund. Math., v. 28 (1936), pp. 197—202. Piccard, Sur un probleme de la theorie des relations. Mathe- matica, v. 13 (1937), pp. 55—58. Marcus, Sur les ensembles independants dans la theorie des relations. Monalsh. Math., v. 63 (1959), pp. 244—255. F о d о г, On two problems concerning the theory of binary rela- tions. Publ. Math. Debrecen, v. 1 (1950), pp. 199—200, F о d о r, On a theorem in tlie theory of binary relations. Compo- sitio Math., v. 8 (1951), p. 250, F odor, On a problem concerning the theory of binary relations. Xieuw Archiv voor Wiskunde, v. 23 (1951), pp. 247—248. L a z a r, On. a problem in the theory of aggregates. Composilio Math.,v, 3 (1936), p. 304. Griinwald. Uber einen mengentheoretischen Satz. Math. Fiz. Lapok, v. 44 (1937), pp. 51—53, Bagemihl, The Baire Category of independent sets. Compositio Math., v. 13 (1956), pp. 71—75. E r d о s and G. F о d о r, Some remarks on set theory. V, Acta. Sci. Math. Szeged, v. 17 (1956), pp. 250—260; VI, v. 18 (1957), pp. 243—260. Gallaf, Cber extreme Punkt- und Kantenmengen Annales. Un. Sci. Budapest, v. 2 (1959), pp. 133—138. ЛИТЕРАТУРА 323 13.4 Р. Т и г a n. Eine E.xtremalaufgabe aus der Graphentheorie. Math. Fiz. Lapok, v. 48 (1941), pp. 436-452. P. Turan, On the theory of graphs. Colloq. Math., v. 3 (1954), pp. 19-30. К. Z a r a n k i e w i с z, Sur les relations symetriques dans I'ensemble fini. Colloq. Math., v. 1 (1947), pp. 10—14. P. E r d о s and A. H. Stone, On the structure of linear graphs. Bull. Amer. Math. Soc., v. 52 (1946), pp. 1087—1091. P. Erdos, Some theorems on graphs. Reveon Lematcmalika, v. 9 (1955), pp. 13-17. 13.5 F. P. R a m s e y, On a problem of formal logic. Proc. London Math. Soc. (2), v. 30 (1930), pp. 264—286. Т. Skolem, Ein kombinatorischer Satz mil Anwendung auf ein lo- gisches Eiitscheidungsproblem. Fund. Math., v. 20 (1933), pp. 254—261. P. Erdos and R. R a d o, A combinatorial theorem. J. London Malh. Soc., v. 25 (1950), pp. 249-25.-». P. Erdos and G. S z e k e r e s, A combinatorial problem in geo- metry. Compositio Math., v. 2 (1935), pp. 463—470. R. Rado, The distributive law for products of infinite series. Quart. J. Math., Oxford Ser., v. 11 (1940), pp. 229—242. W G о о d m a n. On set of acquaintances and strangers at any parly. Amor. Math. Monthly, v. 66 (1959), pp. 778—783. M. G 1 с a s о n and R. E. G r e e n w о о d, Combinatorial relations and chromatic graphs. Canad. J. Math., v. 7 (1955), pp. 1—7. P. Erdos, Some remarks on the theory of graphs. Bull. Amer. Mali). Soc., v. 53 (19'i7), pp. 292—294. P. Erdos and R. Rado, Combinatorial theorems on classifications of subsets of a given set. Proc. London Math. Soc., v. 2 (1951), pp. 417—439. P. Erdos and R. Rado, A partition calculus in set theory. Bull. Amor. Math. Soc., v. 62 (1956), pp. 427—489. 13.6 С. E. Shannon, Tlie zero error capacity of a noisy channel. Trans- actions 1956 Symposium Information Theory, Institute of Radio Engineers, v. IT-2, pp. 8—19. Есть русский перевод: Шен- нон К., Пропускная способность канала с шумом при пуле- вой ошибке. В сб.: Ш e n н о и К., Работы по теории информа- ции и кибернетике, ИЛ, M., 1963, 464—487. Глава 14 14.1 P. Erdos and N. G. d e В r u i j n, A colour problem for infinite praphs and a problem in the theory of relations. Indagationes Math., v, 13 (1951), pp. 369-373. 21* 324 ЛИТЕРАТУРА Р. Е г d о s and R. R a d о, Partition relations connected with the chromatic number of graphs, J. London Math. Soc., v. 34 (1959). pp. 63-72. R. L. Brooks, On colouring the notes of a network. Cambrido'е Philos. Soc., v. 37 (1941), pp. 191—197. J. Mycielski, Sur le coloriage des graphcs. Colloq. Math., v. 3 (1955), pp. 161-162. 14.2 Е. А. N о г d h a u s and J. W. С a d d и in, On complementary graphs. Amer. Math. Monthly., v. 63 (1956), pp. 175—177. А. А. Зыков, О некоторых свойствах линейных комплексов. Ма- тем. сб., т. 24 (66), 2 (1949), стр. 163—188. 14.3 G. A. Dirac, Note on the colouring of graphs. Math. Z., v. 54 (1951), pp. 347-353. G. A. Dirac, Some theorems on abstract graplis. Proc. London Mach. Soc. (3), v. 2 (1952), pp. 69—81. G. A. Dirac, A properly of 4-chromatic graplis and some remarks on critical graphs. J, London Math. Soc., v. 27 (1952), pp. 85—92. G. A. Dirac, The structure of A'-chromalic graphs. Fund. Math., v. 40 (1953), pp. 42—55. G. A. Dirac, Circuits in critical graphs. Monatsh. Math., v. 59 (1955), pp. 178-187. G. A. Dirac, A theorem of B. L. Brooks and a conjecture of IL Hadwiger. Proc. London Math. Soc. (3), v. 7 (1957) pp. 161-195. " J. В. К ell у and L. M. К e 11 у, Paths and circuits in critical graphs. Amer. J. Math., v. 76 (1954), pp. 786—792. R. С. Read, Maximal circuits in critical graphs. J. London Math Soc., v. 32 (1957), pp. 456—462. В. Zeidi, Uber 4- und 5-clirome Graphen. Monat.sh. Math., v. 62 (1958), pp. 212—218. 14.4 G. D. В i r k h о f f, A determinant formula tor the number of ways of colouring a map. Ann. of Math. (2), v. 14 (1912), pp. 42—46. G. D. Birkhoff, On the number of ways of colouring a map. Proc. Edinburgh Math. Soc. (2), v. 2 (1930), pp. 83—91. U. Whitney, A logical expansion in mathematics. Bull. Amcr. Math. Soc., v. 38 (1932), pp. 572—579. IL Whitney. The colouring of graphs. Ann. of Math. (2), v. 33 (1932), pp. 688-718. IL W h i t n e у, A set of topological invariants for graphs. Ашсг, J. Math., v, 55 (1933), pp. 231—235. ЛИТЕРАТУРА 325 Глава 15 15.1 R. F г u с h t, Die Gruppe des Pelcrscnschen Graphen und der Kanteii- systeme dor rogularen Polyeder. Comment. Math. Helv., v. 9 (1937), pp. 217—223. I. N. К a g n о, Dcsargues' and Pappus' graphs and thoir groups. Amer. J. Math., v. 69 (1947), pp. 859—862. I. N. Kagno, Linear graphs of degree ^6 and their groups. Cor- rections ibid., v. 69 (1947), p. 872; v. 77 (1955), р. 392. G. Poly a. Kombinatorische Anzahlbestimmungen fur Gruppcn, Graphen und chemische Verhindungen. Acta. Math., v. 68 (1937) pp. 145—254. 15.2 А. С а у 1 e у, The theory of groups, graphical representation. Math. Papers, v. 10, pp. 403—405. A. Cayley, On the theory of groups. Ibid., v. 10, pp. 323—330; v. 11, pp. 365—367. • R. A. R a n k i n, A campanolorical problem in group theory. Proc. Cambridge Philos. Soc., v. 44 (1948), pp. 17—25. T J Fletcher, Campanological groups. Amer. Math. Monthly, v. 63 (1956), pp. 619—626. D J D i с k i n s о ri. On Fletcher's paper: «Campanological groups». Amer. Math. Monthly, v. 64 (1957), pp. 331—332. E. S. Rapapurt, Cayley color groups and Hamilton lines. Scripta Math., v. 24 (1959), pp. 51-58. 15.3 В. Frucht, IIerstellung von Craphon mit vorgegebener abstrakter Gruppe. Compositio Math., v. 6 (1938), pp. 239—250. R Frucht, Graphs of degree three with a given abstract group. Canad. J. Math., v. 1 (1949), pp. 365—378. R F r u с h t, On groups of repeated graphs. Bull. Amer. Math. Soc., v. 55 (1949), pp. 418—420. R. Frucht, On the construction of partially ordered systems with a given group of automorphisms. Rev. Un. Mat. Argentina, v. 13 (1948), pp. 12—18. G T. Tranque, The type in cubic graphs. Gaceta Mat., (1), v. 5 (1953), pp. 11—23. H. I z b i с k i, Regulare Graphen 3., 4. und 5. Grades mit vorgegebe- ncn abstrakten Automorphismengruppen, Farbenzahlen und Zu- sammcnhangen. Monatsh. Math., v. 61 (1957), pp. 42—50. H. I z b i с k i, Unendliche Graphen endlichen Grades mit vorgegebc- nen Eigenschafton Ibid, v. 63 (1959), pp. 298—307. H I z b i с k i, Regulare Graphon beliebigen Grades mit vorgegebenen Eigenschaften. Ibid., v. 64 (1960), pp. 15—21. G. S a b i d u s s i, Graphs with given group and given graph-theore- tical properties. Canad. J. Math., v. 9 (1957), pp. 515—525. ЛИТЕРАТУРА Sabid us si, On tlio minimum order of graphs with given auto- morphism group. Monatsh. Math., v. 63 (1959), pp. 124—127. Sabid us si, Graphs with given infinite groups. Ibid., v. 64 (1960), pp. 64—67. Sabid us si, Graph multiplication. Math. Z., v. 72 (1960) pp. 446—457. Sabidussi, On a class of fixcd-poinl-free graphs. Proc. Aruer. Math. Soc, v. 9 (1958), pp. 800—804. Sabidussi, The composition of graphs. Duke Math. J., v. 28 (1959), pp. 693—696. Н а г а г у, On the group of llie composition of two graphs Duke Math. J., v. 26 (1959), p. 29—34. В i г k h о f f. On groups of automorphisms, Rev. Un. Math Ar- gentina, v. 11 (1946), pp. 155—157. . Т. Т u 11 e, A family of cubical graphs. Proc. Cambridge Philos Soc., v. 43 (1947), pp. 459-474. S. M. Coxeter, Self-dual configurations and regular graplis Bull. Amer. Math. Soc., v. 56 (1950), pp. 413—455. Frucht, A one-regular graph of degree three. Canad. J. Malli, v. 4 (1952), pp. 2'i0—247. 15.4 Whitney, Congruent graphs and the connectivity of graphs Amer. J. Math., v. 54 (1932), pp. 150—168. Whitney, On the classification of graphs. Ibid., v. 55 (19Уо) pp. 236-244. Whitney, 2-isomorphic graphs. Ibid., v. 55 (1933), pp. 245—254. M. Foster, Geometrical circuits of electrical networks. Bell. Tel. Syst. Techn. Publ. B-653; также Transactions Amer. Inst. Elec. Eng., y. 51 (1932), pp. 309—3!7. К г а u s z. Demonstration nouvelle d'un theoreme de Whitney sur Ics reseaux. Mat. Fiz. Lapok, v. 50 (1943), pp. 75—85. ИМЕННОЙ УКАЗАТЕЛЬ Аарден-Эренфест (van Aarden- ne-Ehrenfest) 56 Багемил (Bagemihl) 269 Беблер (Baebler) 100 Бекман (Beckman) 68 Биркгоф (Birkhoff G.) 307 Биркгоф (Birkhoff G. D.) 295 Бол (Bol) 80 Борувка (Boruvka) 81 Боствик (Bostvick) 278 Ботт (Bott) 80 де Брейн (de Bruijn) 56, 284 Брукс (Brooks) 285 Важоньи (Vazonyi) 59, 64 Вайсфельд (Weiszfeld) 59 Винер (Wiener С.) 66 Винер (Wiener N.) 246 Винстен (Winsten) 68 Гаддам (Gaddum) 285 Галлаи (Gallai) 75, 116, 269 Гейл (Gale) 183 Глисон (Gleason) 276 Гольдберг (Goldberg) 104 Грин (Green) 104 Гринвуд (Greenwood) 276 Грюнвальд (Grunwald T.) 59 Гудыан (Goodman) 276 Далмидж (Dulmage) 162, 166 Данциг (Dantzig) 72 Дезарг (Desargues) 302 Джобек (Dziobek) 80 Джонсон (Johnson) 72 Диксон (Dickson) 277 Дилворт (Dilworth) 220, 222 Дирак (Dirac) 74, 110, 116, 289, 291-293. Душник (Dushnik) 227 Жакотен-Дюбревль (Jacotin-Dub- reil) 244 Зыков А, А. 288 Избипкий (Izbicki) 307 Каньо (Kagno) 302 Келли (Kelly J. В.) 285, 290 Келли (Kelly Б. M.) 285, 290 Кёниг Д. (Konig D.) 10, 66, 177, 256 Клейн Э. (Klein) 277 Коксетер (Coxeter) 307 Комм (Кошт) 231 Косслер (Kossler) 81 Краскал (Kruskal) 81 - Кэли (Cayley) 78-80, 303 Люка (Lucas) 57, 66 Майберри (МауЬеггу) 80 Макай (Makai) 278 Макгир (McGuire) 68 Маклейн (MacLane) 104, 210 Маркус (Marcus S.) 269 Менгер (Menger) 252, 256, 258 Мендельсон (Mendelsohn) 162, Миллер (Miller E. W.) 227 Миллер (Miller G. A.) 152 Морган де (De Morgan) 9 Мыцельский (Mycielski) 285 ИМЕННОЙ УКАЗАТЕЛЬ 328 Opo (Ore 0.) 67, 92, 100, 135, 152, 153, 162, 210 Неттльтон (Nettleton) 104 Нетто (Netto) 268 Ыордхауз (Nordhaus) 285 Норман (Norman) 114 Папп (Pappus) 302 Петерсон (Petersen) 168, 302 Пикар (Piccard) 268 Пойа (Polyan) 80, 303 Прюфер (Prufer) 79 Радо (Rado) 278 Райзер (Ryser) 183 Рамсей (Ramsey) 273—279 Рапапорт (Rapaport) 305 Редей (Redei) 188 Риге (Riguet) 244, 246 Рид (Read) 291 Риордан (Riordan) 80 Роббинс (Robbins) 187 Роуз-Болл (Rouse-Ball) 66, 262 Рэйнич (Rainich) 244 Сабидусси (Sabidussi) 307 Секереш (Szekeres) 277 Серпинский (Sierpinski) 268 Скорца (Scorza) 151 Татт (Tutte) 76, 285, 307 Тремо (Tremaux) 66 Тэрри (Tarry) 57, 66 Уайтпп (Whitin) 80 УИТНИ (Whitney) 295, 296, 299, 308, 310, 312 Уленбек (Uhlenbeck) 114 Фалкерсон (Fulkcrson) 72, 134 Фодор (Fodor) 269 Форд (Ford) 68, 134 Фрухт (Frucht) 301, 302, 305-i 308 Харарп (Нагагу) 100, 114 Хедвигер (Hadwiger) 292, 294 Хиггинс (Higgins) 178, 181 Холл М. (Hall M.) 149, 167 Холл Ф. (Hall P.) 144 Хусими (Husimi) 114 Царанкевич (Zarankiewicz) 273 Цермело (Zermelo) 118 Чепмеп (Chapman) 152 Шеннон (Shannon) 278, 281 Шоке (Choquet) 81 Шпильрайн (Szpilrain) 227 Шур (Schur) 277 Шю (Sliu) 152 Эджид (Egyed) 187 Эйлер (Euler) 9, 53—56, 58, 166 Эрдёш (Erdos) 59, 75, 116, 269, 276-279, 284 Ярник (Jarnik) 81 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Автоморфизм двойственный 236 — обратный 236 Автоморфизмов группа 300 Аксиома выбора 118 Аксиомы метрики 41 — структуры 224 Базис транспозиций 80 Бернштейна теорема 146 Биркгофа формула 295 Блок 111, 191 Блоковое множество 111, 191 Брэттопа проблема 189 Верхний отрезок 218 Вершина 11 — внешняя (части) 102 — внутренняя (маршрута) 34 — — (части) 102 —дефицитная 170, 204, 218 —, достижимая из а 184, 199 —, — — множества А 253, 256 —— изолированная 14 —, инцидентная ребру 12 —— конечная (маршрута) 34 — — (ребра) 12 — концевая (графа) 77 —, кратность 127 — начальная (маршрута) 34 — — (ребра) 12 —, непосредственно предшеству- ющая Ь 206 —,— следующая за а 206, 21G — обратно дефицитная 218 —, относящаяся с высотой 91, ! 82 —Промежуточная 34, 206 — разделяющая 112 —~ разрезающая 112 Вершпна соединяющая (части) 102 — средняя 44 Вершинная связность 103 Вершины бисвязанные 185 — взаимно связанные 185 — несравнимые 193 — ориентированно-циклически- реберно связанные 185 — связанные 36 — сильно связанные 185 — — циклически связанные 110 — смежные 30 — сравнимые 192 — циклически-реберно связан- ные 105, 106 —, эквивалентные по достижи- мости 184 —,— по «-достижимости 200 Вес дерева 85 — — в вершине v 85 Ветвь 78, 85 — с весом 85 Выбирающая функция 118 Галуа замыкания 233 — операции замыкания 233 — связь 232 — — инволютивная 238 ——совершенная 234 — -, -в Р 234 — соответствие 232 '-, — двойственное себе 236 Гамильтопов центр 75 —- цикл 70 Гамильтонова цепь 71 Гейла — Райзера теорема 183 Гомоморфизм 107—111, 189 —кратный 108 — независимый 109 330 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Гомоморфизм простой 108 — разделенный 109 — связный 109 — элементарный независимый 109 — — связный 109 Гомоморфный образ графа 107 Гранди функция 282 Граничные точки ребра 11 Граф 11 — ациклический 189 — базисный 194, 206 — без циклов 77 — бесконечный 16 — бисвязный 186 — (вершинно) критический 289 — взаимно связный 186 —воспроизведения 211 — всесмежный 261 — двудольный 27, 134 — двусторонний 134 — Дезарга 302 — (зависимости) сигналов 279 — звездный 23, 263 — исключения 127 — — максимальный 127 — конечный 16 — критический 289 — локально конечный 16 — максимальный сильно сингу- лярный 131 — — сингулярный 131 — накрывающий 262 — неориентированный 12 — обратный 15 — однородный степени я 18, 21 —, определяемый взаимно одно- значным отображением ила подстановкой 39 — ориептированно-пиклически замкнутый 189 — ориентированный 12, 184 — Паппа 302 — передаточный 279 — Петерсена 302 — плоский 16 — покрывающий 262 — полный 14 — — ориентированный 14 —• — с Петлями 15 —потомства 211 — почти однородный 152 Граф, произвольно вычерчивае- мый из вершины а 96 — связный: 36 — сильно ориентированно-цик- лически замкнутый 191 — — ориентированно-цикличе- ски-реберно связный 190 — — связный 186 ——циклически замкнутый 112 ———связный 110, 113 — смежности ребер 32 — смежностный 32 — смешанный 13 — соединяющий 103 —,соотнесенный неориентиро- ванный 15 — строгого частичного упорядо- чения 216 — транзитивный 191 — цветной Кэлли 303 —циклически замкнутый 106 —частичного упорядочения 216 — чередующейся композиции 201 — ^--раскрашиваемый 282 — ^--ребро связный 102 — Д-хроматический 282 — <-вершинно связный 103 Графа транзитивное замыкание 192 Графы изоморфные 13 — реберно изоморфные 307 — сингулярно связанные 131 — циклически изоморфные 310 Группа полная мономиальпая 301 Двойственное разбиение (чис- ла) 181 Двойственность между верши- нами и ребрами графа G 32 Декартова сумма графов 51 Декартово произведение графов 50 Дерево 77 — максимальное 128 — с корнем 78 — Хусими 114 Дефицит 138, 202 — максимальный 139 — множества А относительно В 257 — — — — — максимальный 257 331 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Дефицит обратный 203 — ребер 259 Дефицитов ограниченность 139 Деформация 208 — простая 208 — циклическая (паросочетапия) 169 Диаметр 43, 82 — протяженности 45 Дилворта теорема 220 Дирака теорема 116 Дисперсия 44 Дихотомия но полу 212 Дополнение (элемента) 237 — — ортогональное 237 — — полярное 237 — части 23 Дополнительная часть 23 Дуга 12 Душника — Миллера теорема 227 Дюбрейля условие шестиуголь- ника 247 Жордана — Гельдера свойства 208, 210, 216 — — теорема для главных ря- дов в группах 211 — — — — композиционных ря- дов 210 Задача Киркмана см. Киркмапа задача 268 — о браке или о танцах 147 — о бродячем торговце (о ком- мивояжере) 71 — о движении транспорта 187 — о Кёпигсбергских мостах 9, 53 — о лабиринте 57, 64 — — —, метод Винера 66 — — —, — Терри 57, 66 — о минимальном соединении 81 — о назначениях 147 — о перевозчике 51 — о пяти ферзях 262 — о разделении 52 — о ревнивых мужьях 52 Задача о Ханойской башне 52 — о шахматном копе 70 — Эстер Клейн 277 Законы дистрибутивности 228 — поглощения 224 Замкнутые элементы 234 Запрещенная составляющая множества Е 130 Инволюция 237 Индекс компонент 47, 289 — связности вершины 114 Инцидентности отношение 12 Исключение конечного типа 127 Квазигруппа 166 Квазиупорядочение 191 Кёнига теорема 177, 256 Киркмана задача о пансионе для девушек 268 Класс эквивалентности неосо- бый 28 — — особый 28 — — элемента я 27 Клика 266, 276 Компактное реберное разделе- ние 196 Компонента дефицитная 172 — связная 36 — совершенная 172 Конечность цепей (из вершины) 258 — — (между вершинами) 206 Контур 35 Концевые точки (маршрута) 35 — — (ребра) 11 Концы (маршрута) 35 — (ребра) 11 Корень дерева 78 Кратность (ребра) 17, 21 Куратовского — Хаусдорфа принцип максимальности см. Принцип максимальности Хаусдорфа — Куратовского 120 Кэли задача 80 — таблица 166 — формула 78, 80 — цветной граф 303 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ 332 Латинский квадрат 106 — — частичный 167 — — — максимальный 167 Лес 177 Лист 106, 189 Листовая композиция 108, 190 Листовое множество 106, 189 — — особое 106 Маршрут 34 — возвращающийся секущий 252, 255 — двустороине-бескоиечпый 35 — длины re 35 — неориентированный 35 — нетривиальный 35 — односторонне-бесконечный 35 — ориентированный 35 — циклический 35 Матрица бистохастическсп 1R4 — инцидентности 31 — мер 31, 50 — перестановочная 306 — смежности (вершин) 30 — — ребер 31 — стохастическая 164 Мапгера теорема 252, 256 Мера (ребра) 32, 50, 68 Метод чередующихся ценен 107 Множества, сопоставленные при паросочетапии 142 —, я-вершиппо разделенные 252 —, т-реберно разделенные 255 Множество бел дефицита 140, 257 — вершин 11 —вполне упорядоченное 117 —всесмежпое 261 —дефицитное 171 — доминирующее 260 — — минимальное 260 ——обратное 261 — достижимое 200 — зависимое 266 — замкнутое 225 — критическое 139, 258 — — минимальное 140, 173 — максимального дефицита 139 — накрывающее 269 — независимое 219, 268 — — максимальное 266 Множество, не имеющее ^-дефи- цита 179 — несвязанное 266 — покрывающее 262 — полностью зависимое 266 — порождающее 185, 218 ——минимальное 185, 218 — прообразов 107 — разделяющее 176, 255 — — согласованное 176 — — — конечно минимальное 177 ——,—с паросочотанием М 176 — различных общих представи- телей 148 — ребер разделяющее 255 — связанное 2.66 — сильно зависимое 220 — соседства 22 — субдоминирующее 261 — упорядоченное 29 — — максимальное 121 — частично упорядоченное 29 Мост 105 Моток 97 Мощность (ребра) 31 Мультипликативная размер- ность (частичного упорядо- чения) 228 Наполнение графа С 129 Неподвижная точка отображе- ния 40, 90 Неравенство треугольника 41 Нижний отрезок 218 Нуль-граф 14 Нуль-маршрут 35 Ортогональность 237 Остов 129 Отклонение вершпп 44 — — среднее 44 — ребер среднее 44 Отношение аптирефлексивпое 27, 240, 242 — ациклическое 216, 242 — бинарное 25 — включения 28, 184 — — множеств 29 —, двойственное себе 236, 240 — дополнительное 25 833 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Отношение замкнутое 241 — замыкания 225 — непосредственного потомства 211 — пулевое 25, 242 — обратное 26 — одинаковости 25 — отличия 25 — полного упорядочения 117 — рефлексивное 27, 242, 240 — самотранзитивное 244 — симметрическое 26 — слабо симметрическое 240 — — транзитивное 244 — собственного включения 29 — строгого включения 29 — — частичного упорядочения 29, 216 — тождественное 242 — транзитивное 26, 242 — универсальное 25 — упорядочения 29 — частичного упорядочения 28, 216 — эквивалентности 27, 242 — /?' следует из отношения Л 26 — R' содержит отношение R 26 Отношений коммутативность 247 — слабая коммутативность 247 Отношения взаимно трапзитив- пые 243 — дифункциопальные 244 — степень 242 — транзитивное замыкание 243 — Феррерса 246 — чередующегося произведения 245 Отображение взаимно однознач- ное 39 — мпого-однозиачпое 88 О-^пцаппе 25 Паросочетапие 142, 258 — вершинно-реберное инци- дентное 93 — максимальное 168 — правильное 143 — реберно-вершинное инцидент- ное 93 —- совершенное 147 Паросочетание частичное 142 Паросочетания взаимные 145 — инцидентные 93 — совместные 178 Пересечение отношений 26 — частей 23 Перманент 162 Петля 15 — двойная 17 — однократная 17 Платоповы тела 18 Подграф 23 — пустой 266 Покрывающий суграф графа G 23, 262 Полная подструктура относи- тельно структурного пересе- чения 236 Полное кольцо пересечений 225 Полуостров 101 — ранга k 101 Полярность 237 Порождающая часть графа 194 Порядковая размерность (час- тичного упорядочения) 227 Порядок вершины при отобра- жении 39, 90 — графа 44 Потомок 211 Правильные многогранники 18 Предок 211 Представление графа G в виде формального произведения 24 Принцип включения — исключе- ния 125 — максимальности Хаусдор- фа — Куратовского 120 — — Цорна 122 — суммы цепи 123 —трапсфинитной индукции 117 Проблема четырех красок 9, 294 Произведение графов 48 — множеств 12 — — декартово 12 —— — прямое 12 — отношений 242 — упорядочений 228 Пропускная способность ребра 31 "~~" Протяженность 45 Процесс постепенного покрыМ- иия графа 67 334 ПРЕДМЕТНЫЙ УИЛЗ.\Г1:;1Ь Процесс редукции индекса 68 — трансфинитного построения 121 Путь 35 Радиус графа 43 — протяженности 45 Гадо теорема 137 Разбиение множества 28 Разделяющее множество (в це- пи множеств) 118, 252 Разложение частичного упоря- дочения 217, 220, 222 — — — независимое 222 Рамсея теорема 273 Раскраски функция 282 Раскрашивании полином 294, 297 Расстояние 41 — в смысле данной меры 68 Ребер независимое семейство 269 — покрывающее семейство 262 Реберная связность 102 Ребра кратность 17, 21 Ребра секущие 248 — —, размеченные по простым цепям 251 — сильно ориептироваппо-цик- лнчески-реберно связанные 190 — — циклически-связанные 110 — смежные 31 Ребра 11 — ациклическое 185 — внешнее 101 — внутреннее 102 —, входящее в (подходящее к, заходящее в) вершину Ь 12 —, выходящее из (отходящее от. исходящее из) вершины а 12 Ребро излишнее 194 —, инцидентное вершине 12 — касающееся 101 — концевое 77 — неориентированное 12 — ориентированное 12 — ориентированно циклическое 185 — разделяющее 105 — разрезающее 105 Ребро связывающее 101 — соединяющее 101 — существенное 198 — циклическое 105 Редей теоремы 188 Редукционное множество 131 Редукция дерева 79 Родитель 212 Сабли Магомета 53, 54 Свойство включения 124 — — (или исключения) [«оиеч- цого тина 124 — исключения 124 ——конечного типа 124 Серпипского— Пикара теорема 268 Сеть 12 Сигналы зависимые 279 — независимые 279 Симметрическая группа 80 Сингулярная реберная замена 131 — циклическая замена 132 Скелет 129 Сопоставление при паросочета- нии 142, 258 Сочетания /.--связанные 267 Ствол дерева 78 Степень (графа) в вершине я 17, 21 ————— локальная 17, 21 — однородного графа 18, 21 Структура 224 — дистрибутивная 228 — полная 224 — с дополнениями 237 Структурная операция 223 Структурное объединение 223 — пересечение 223 Суграф 22, 202 — однородной первой степени 147 — покрывающий 23. 2(13 — — собственный 265 Сумма отношений 26 — частей 23 — — прямая 24 — — — по ребрам 24 — элементов матрицы по столб- цам 164 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ 835 Сумма элементов матрицы но строкам 164 — — — полная 164 Суммируемое по цени c"'.>i'ic"i!0 123, 124 Теорема о вершинном разделе- нии 252 — о гомоморфизме 109, 190 — о паросочетании 138, 141 — о реберном разделении 254 — о секущих цепях 248 — о системах различных пред- ставителей 144 Терм-граф 160 Терм-ранг 161 Транзитивное замыкание гра- фа 191 — — отношения 243 Транспозиция 80 — двух вершин 42 Трапсфинитпое построение 121 Турана теорема 270 Удвоения процесс 16 Узел 12 Уитни выражение для полино- ма раскрашивании 296 — теорема 308 Упорядочение слабое 192 Фактор 24 Феррерса диаграмма 246 — отношения 246 Функции дефицита 138 Xapapii соотношение 114 Хаусдорфа — Куратовского принцип максимальности см. Принцип максимальности Хаусдорфа — Куратовского Хедвигера предположение 292 Хорда 293 Хроматическое разложение 282 — число 282 Хусимп деревья 114 Центр (в сомкнутой цепочке) 274 Центр гамильтонов см. Гамиль- тонов центр — графа 43 — дерева 84 — масс дерева 85 — тяжести графа 44 — протяженности 45 Цепи взаимно простые 208 — деформационно эквивалент- ные 209 — покрывающие граф 55 — секущие 250 Цепочка сомкнутая 274 Цепь (множеств) 118, 121 — (ребер) 35 — дефицитная 170 — ориентированная максималь- ная 206, 216 — простая 35 — — диаметральная 43, 82 — — — по протяженности 45 — — длиннейшая 45 — — наименьшей длины 41 — — полная 73 — — радиальная 43 — — — по протяженности 45 — — связывающая 252 — простая типа цикла 73 — связывающая 252 — чередующаяся 167, 198 Цермело теорема 118 Цикл 35 — концевой 115 — отображения 40, 90 — — обобщенный 89 — простой 35 — — разорванный 295 Циклический ранг 88 Цикломатическое число 88 Цорна лемма 122 Части непересекающиеся (по вершинам) 24 — — по ребрам 24 Частичное упорядочение 28, 216 — — локально конечное 222 — — строгое 19, 216, 242 Часть графа 2^ — — не более чем первой степе- ни 204 ' ' ' ——————— максимальная 204 ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ 838 Часть, покрывающая граф 23 Чередующаяся цепь см. Цепь чередующаяся Чередующееся расширение 168 — семейство секущих ребер 248, 251 Чередующийся цикл 109 Четырехугольника условие 210, 243 Число вершинного покрытия 265 — — соединения 103 — (вершинной) независимости 267 —- доминирования 262 — протяженности 45 — реберного покрытия 265 —— — соединения 101 — реберной независимости 209 —— пикломатпческое см. Цикло- матическое число Шестиугольника условие 247 Штейпора тройки 268 Эйлеров граф 54 — цикл 54 Эйлерова цепь 56 d-дефицпт 179 G-мпожество 22 — обратное 22 ^--раскраска графа 282 Af-множество 176 Л/-образ 172 Л-граф 136 «-ребро 198 ос-цепь 198 ю*-ребро 198 {Г}-множество 123 б-ыпожество минимальное 173 (ст, си*) -маршрут чередующийся правильный 213 (я, »*)-цепь 198 ^UAI-.r/tVrtn ГЕ1.1 Предисловие ........................ Глава 1. Векторное исчисление ................. § I*. Понятие вектора . ................. ."". 1. Предварительное определение вектора ........... \?^ Отношения эквивалентности ............... 3. Окончательное определение вектора ........... 4. Векторы на прямой, на плоскости и в пространстве ..... § 2*. Векторы на прямой ................... 1. Ориентации прямой . ................. 2. Длина и величина вектора на прямой ........... 3. Отношение векторов на прямой ............. 4. Сложение векторов на прямой. Лемма Шаля ........ 5. Алгебраические свойства линейных операций ........ 6. Теорема об изоморфизме ................ § З*. Линейные операции над векторами на плоскости и в пространстве 1. Определение линейных операций ............. 2. Алгебраические свойства линейных операций ........ 3. Линейная зависимость ................. 4. Геометрический смысл линейной зависимости ........ 5. Базисы и координаты ................. 6. Проекции и координаты ................ 7. Преобразование координат при замене базиса ........ Дополнение. Теорема о ранге матрицы ...'...... § 4*. Ориентации прямой, плоскости и пространства ........ 1. Понятие ориентации .................. 2. Правые и левые ориентации ............... 3. Произведения ориентации . .............. 4. Стороны прямой на плоскости и плоскости в пространстве . . . 5. Деформации базисов и ориентации ............ 6. Резюме. . ...................... Дополнение. О понятии угла ............. § 5*. Метрическая теория векторов ............... 1. Длина вектора и угол между векторами .......... 2. Скалярное произведение векторов ............ 3. Применение скалярного умножения к доказательству геометри- ческих теорем . ................... 4. Выражение скалярного произведения в координатах ..... 5. Ортонормированные базисы ............... 6. Ортогональные матрицы . ............... § 6. Поливекторы . .'................... 1. Бивекторы . .................... 2. Линейные операции над бивекторами ........... 3. Линейная теория бивекторов .............. 4. Метрическая теория бивекторов ............. I*