67604

Планарность и раскраска графов

Лекция

Математика и математический анализ

Такая функция называется плоским мультиграфом. Внутренние грани плоского мультиграфа называется конечная плоскость окруженная простым циклом и не содержащая внутри себя никаких ребер. Называется её границей.

Русский

2014-09-12

97.5 KB

2 чел.

Лекция №15

Планарность и раскраска графов

опр || мультиграф называется планарным если его можно нарисовать на плоскости так, что  2 дуги (ребра) либо не имеют общих точек, либо имеют общие точки, совпадающие с вершинами графа.

В  точках пересечения сходятся лишь дуги инцидентные вершине, совпадаюшей с точками пересечения.

Такая функция называется плоским мультиграфом.

Внутренние грани плоского мультиграфа называется конечная плоскость окруженная простым циклом и не содержащая внутри себя никаких ребер.

Простой цикл ограничен. Называется её границей.

Часть плоскости состоящая из точек принадлежащих графу и какой либо её плоскости называется её высшей степенью.

Для связанных плоских мультиграфов выполняется соотношение Эйлера

n – количество вершн

m – количество ребер

- гр. внеш

Критерий планарности

Теорема Плантрагина-Куратовского

Теорема || Граф планарен тогда и только тогда, когда ни одна из его подграфов не гомопотрофна следующим графам

        

Раскраской вершин графа (или ребер мультиграфа) называется сопоставление вершинам определенных цветов.

Раскраска называется правильной если смежные вершины (ребра) окрашены в разные цвета.

Наименьшее число цветов для каждого  прав. раскраски графа G называется хроматическим числом и обозначается X(G)

1)

2)

3)

Для хроматического индекса свойства:

1)

2) G граф

Транспортные сети

Транспортной сетью называется орт граф

для которого выражаются условия:

1)  одна и только одна вершина называется источником

множество дуг заходящих в точку

2)  -//- верш .  называется истоком т.ч.

3) Каждой дуге  сопоставляется число (целое и не отрицательное) т.ч.  называемое пропускной способностью дуги

4) Вершины отличные от источника и истока называются промежуточными

опр || потока

Функция  определенная на множестве X граф D и принимающая целочисленные значения называется потоком транспортной сети D, если

1) для  дуги

2) для  промежуточной дуги x

2,5) для  промежуточной вершины

Сколько вышло столько и вошло.

опр ||  называется насыщенным, если поток по ней равен ее пропускной способности

опр || поток  называется полным, если его путь из  в  содержит хотя бы одну насыщенную дугу

опр || Поток называется максимальным, если   принимает максимальное значение по сравнению с другим допустимым потоком.

Замечан || максимальный поток является полным, но обратно не верно.

Алгоритм построения полного потока

1)

2) из  удаляем дуги являющиеся насыщенными

3) ищем в  простую цепь

, если не находим, то конец.

- искомый поток по определению

4) Увеличим поток по всем дугам на одинаковую величину т.ч. хотя бы одна дуга из  является насыщенной, потоки по остальным не превышают их пропускных способностей


 

А также другие работы, которые могут Вас заинтересовать

28943. Славянский мир. Процесс этногенеза у восточных славян 24 KB
  Славянский мир. Процесс этногенеза у восточных славян. Древнерусская народность явилась тем этническим образованием восточных славян которое возникло в период зарождения и утверждение феодализма в эпоху возникновения государства в процессе формирования расширявшим свою территорию включая в состав Руси неславянские этнические элементы. В ходе Великого переселения народов в Европу хлынули также славянские племена.
28944. Основные этапы становления государственности в Древней Руси и ее особенности 26 KB
  Были разгромлены Волжская Булгария и Хазарский каганат покорены мордовские племена отражен натиск печенегов но война с Византией закончилась неудачно: дружине Святослава с трудом удалось отступить. Святослав попал в засаду печенегов в районе днепровских порогов и был убит. Был укреплен государственный аппарат и решена задача обороны от печенегов.
28945. Принятие христианства и его роль в укреплении государства, духовном объединении древнерусского общества 28.5 KB
  Язычество приводило к изоляции Руси от христианского мира Европы тормозило развитие международных связей и торговли; 2. Язычество мешало стабилизации и укреплению феодального строя на Руси; 3. Монотеизм христианской религии укреплял авторитет княжеской власти способствовал единению Руси; 5. Появляющееся социальное неравенство на Руси требовало новой идеологии которая могла бы оправдать богатство одних и бедность других утешить людей попавших в зависимость от феодала обещая им лучшую жизнь в ином мире.
28946. Русь в период политической раздробленности. Основные политический центры, их государственный и общественный строй 32 KB
  Опираясь на его мощь местные князья сумели установить свою власть в каждой земле. Однако впоследствии между силившимися боярством и местными князьями возникли противоречия и борьба за власть. Боярство обладавшее значительной экономической силой сумело победить князя в борьбе за власть. Реальная же власть была сосредоточена в руках местного боярства.
28947. Борьба русских княжеств с иноземнми захватчиками в XIII веке. Установление ордынского языке и его последствия 29 KB
  Русь переживала период политической раздробленности и шанс объединить силы перед грядущей опасностью был упущен. на съезде золотоордынской знати было принято решение о походе на Русь который возглавил внук Чингисхана Батый. предпринял новый поход на Русь теперь на юг. Приняв на себя основной удар героически сопротивляясь Русь спасла Западную Европу от страшного агрессора.
28948. Возвышение Москвы. Роль московских князей в свержении ордынского ига и создании централизованного Русского государства 32 KB
  Иван I Калита которого называют первым собирателем земель русских перенёс митрополическую кафедру из Владимира в Москву московские князья в своей политике получают в союзники главу русской церкви авторитет которого в то время был очень высок. Политику Ивана I Калиты продолжили его сыновья Симеон Гордый 13401353 и Иван II Красный 1353 1359. После смерти Василия II 1462 великим князем становится его сын Иван III 1462 1505. Человек осторожный расчетливый Иван III последовательно проводил свой курс на покорение удельных княжеств...
28949. Возникновение сословно-представительной монархии в Московском государстве. Внутренняя и внешняя политики Ивана IV 48.5 KB
  Внутренняя и внешняя политики Ивана IV В 16 веке в России складывается сословнопредставительная монархия. в России уже было 25 000 стрельцов. в России разразился настоящий хозяйственный кризис. Последствия опричнины для России были трагичными: 1.
28950. Борьба политических партий за власть в 1917 г. Большевистский государственный переворот 96 KB
  От большевиков в Исполком вошли А. Было принято предложение большевиков об усилении Исполкома путем введения в него по три представителя от партий большевиков меньшевиков и эсеров. На основании этого в состав Исполкома от большевиков были дополнительно введены В. Относительная гибкость партии так же как способность улавливать преобладавшие настроения масс содействовала победе большевиков по крайней мере столько же сколько революционная дисциплина организационное единство и авторитет Ленина.
28951. Борьба политический партий за власть, большевистский государственный переворот 31.5 KB
  Следствием кризиса был Корниловский мятеж в результате которого все большую популярность получили большевики был окончательно потерян авторитет ВП. ЦИК советов и ИСКД создали чрезвычайный орган Комитет народной борьбы с контрреволюцией в который входили меньшевики эсеры и большевики. В это время большевики активизировали работу в советах стали восстанавливать отряды Красной гвардии направили своих агитаторов в корниловские войска Донскую Уссурийскую и Дикую дивизии. Укрепили свои позиции большевики возросло их влияние в народе.