Теория графов и комбинаторика

ГЛАВА 8 . ДВУДОЛЬШЕ ГРАШ. ШИХЗСОЧЬ'ГАНШ -i §8,1. Определение двудольного графа. Теорема Канига §8.2, ПарооочетанЕЯ р двудольных графах. Те _, € мо Холла 'U* §8,3. Мако1а.ольныб паросочетания , . S5I • §8.4. Сиотвш различных 1гх)едс'?ази'гелеЙ . . . . . . . Бй §8.5. Задача о назначениях 5.' ГЛАВА 9. ДЕРЕЕШ,' ФУЩШШЪШНЦЕ CHCTSSl J.paOB К ' РАЗРЕЗОГ.. ILSITPJ К ЩНТРОКДЫ ГГАФОВ. . . . . . (3 , §9.1. Признаки деревьев 53 §9.2. Ориентированные деревья. Упорядочение варшш 55 §9.3. ЦикличеокиЙ и кощ^:.тачеокяй ранги графа. . . 57 §9,4. ^ндаментальные оиотемы циItruJ и разрэзов гра­ фа. . . . . . 5 7 §9.5, Проотранотва циклов и разрезов графа . . . . 59 •I §9.6. Центры и цйнтроиды • пО ШВА 1 0 . И Ш.гаЪТОНОВЧ ГРАФЫ 61 §10,1. Эйлеровы графы 61 §10,2. ГашльтоноБЫ грэ^м гЗ ГЛАВА TI . РАСКРАТСЛ И lUIAHAPHQCTb G4 §11.1. Хроматичеокй индеко и хроматическое шоло графа §11.2. Планарнооть . . . . . . . . . . 66 §11.3. Teop.0i,:j Понтрягина-Куратовокого 68 ГЛАВА 12. НЕКОТОРЫЕ ЗАДАЧИ И .ШОРЛТШ 69 §12.1. Задача о путях о наименьшим чис5лом дуг. . . 69 §12.2. •Задача о путях наименьшей Длина . . . . . . 69 §12.3. Задача о путях наибольшей дани . . .. и ,. 71 §12,4, Определение раоотоянвй между ввриинаш. . . 71 §12.5, Задача р MBKOI. ЗЛЪЯОМ потока в транспортной оати . 72 §12.6. Задача о минимальном покрывающем дереве. , . 75 . f " 2 , 7 . Алгори- 1 раокраоки графов . . . . . . . . . 76 ГЛАВА 13 . ЙЛЕЩЧН' ШДВШАТОЙЯШ 77 §13.1.^ Выборки. Ооновные-вревкла комбинаторики. . . 7? §13.2, Пдроотановки и сочетания 79 §13.3. Биномиальная фог'^ла 80 ,§13.4. ^^абв в т я , .. . . . 81 §13.5. Полиномиальная формула. . . . . 82 91