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

ii:vriin,if,fiM некоторые лоохаточныо условия гак"гьтоновостй ".'ооппм! 1П.4 (Дирак). Связшй -Г1яф (г=СУ)Х)> Р^З я:;,|т(1Т(п rni дьтонолны, если V v e V d c v ) » р/й,. ,!й1КРяп1'ельстБ0. Допустим, что граф (Р не гамильтонов. П у т ь ^ • инннмалькоа чиоло верга^ш ( к Я ) . которпе надо добавить к (j , ч'юбп нолучпгь гаимьтонов граф (?' . Тогда pfS-')- f+K - iiyuri гамиллтонов цшиг в имеет вид: Я l f ) , г'де 1/S - одна из яобавланних зершип; iT , W - вершиш графа (? . Вчр1;[шш iit^ ~ неомежнн. Иначе мокно было бы обойтись без iispcimiH Vf , что противоречит мяншалыюотн к . Вершпа W"? смвкиая id', не может пепооредотвепно оледовать за вершиной I j ' CT.i9SHoft -V . Иначе щпсл Z имел бы wa]s.: тг) м тогда моянс было йы построить гамильтонов не оодвр 'кащий Щ , а это противоречит мпнимальнооти К . Сле- ' дояательно, за верпганой гг' дол:вда следовать вершна, на смежная вершине itT . Таким o<3pa3oMj( «€V: ине i U.cmV]\^ ^ f Н. . Но по условиюКиеи; it ом I(J*)i9i^+)(;j|UHe OMti/-}f+ ^jJU6V;i'-0M иГ } | ^ р,-к . Отсюда p-f-K^p+JiK . Получено противоречие, которое доказывает Teopefjsy. Теорема ТО.5.Связный граф & , имеющий р вершин ( р ^ З ) / >1ЕЛЯе1'0Я ГаМИЛЬТОНОВШЛ, воли \/г^г<^бУ( ТГ .ie OuWz:^(l(TT)h6l(il))>j\ Известны и другйо доотаточнне уогпвия гами;- .тоновоотй vpa- " !|>он. Суть этих условий оподитоя к тому, что в х-рафе должно быть • „,.')отаточяо много ребер. Еоли & - псавдограф, то при анализе- н £ 1 гашльтойсвоотъ HQTJE можнг удалить. Отметим, что необходимость отнокания гашльгоповых ци!игов возкдаает при pgaemiR^ многих гграктпчаских задач. Одной и з таких .задач ^вляатоя -'звеотная задача коммяЕояжэра. ГАЛТ Ц , РАСЖРАСКЛ Й Ш М Н А Н Г ' С Т Ь Рассмотрим ооноЕные вопросы, связанные о раскраской, графов • •И планарйоотью, которые играют важную роль при решении многих иГйг.тйчеокйХ-проблем, например, прп окраоке проводников, объе- •" .TtKUfisF^iKx в кабели, так, чтобы вое ироводникй одного кабеля име- ' • лп разный цвет; при определении минимального числа ячеек памяти. . ЭШ, -шобходатес" дая"некоторой" i ^ o i j p a j M r j D p f ' i i ^ b ^ •МчахишГ^ .шат* Давгоя определения хроматичоского индакоа' и хромадаескм-о,' • 'шсла 1^>афов^ приводятся некоторые оценки»' Формулйр?ш(к^1щязнгН • ,;т®. даанарнсоти rpa$oBi:: . •