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) Увеличим поток по всем дугам на одинаковую величину т.ч. хотя бы одна дуга из  является насыщенной, потоки по остальным не превышают их пропускных способностей


 

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

79079. Владение и право собственности. Владение и держание. Виды. Установление и прекращение владения. Преторские интердикты. Защита добросовестного владения 33.21 KB
  Факты с наступлением которых лицо приобретает право собственности называются способами приобретения права собственности modus cquirendi а те юридические факты в особенности сделки которые служат основанием для приобретения права собственности называются титулом приобретения titulus cquirendi.Способы приобретения права собственности делятся на первоначальные и производные. При первоначальном приобретении права собственности нет праводателя ограниченность правомочий которого могла отразиться на содержании права приобретателя.
79080. Деятельность римских юристов. Формы их деятельности. Значение римской юриспруденции для формирования и развития права. Сабиньянская и прокулянская школы юристов 21.39 KB
  Сабиньянская и прокулянская школы юристов. В произведениях Цицерона формы деятельности римских юристов характеризуются терминами respondere cvere gere а также scribere. Термином respondere обозначается консультационная работа римских юристов дача гражданам обращавшимся к юристам советов по возбуждавшим сомнение вопросам: cvere ограждение интересов данного гражданина при совершении сделок также путем совета не включать какоелибо невыгодное условие и т.
79081. Договор имущественного найма и его виды. Договор найма вещи Поднаем. Прекращение договора найма вещи. Наем услуг. Договор подряда 31.33 KB
  Классическое римское право знало три вида договора locatio-conductio: 1) наем вещей (locatio-conductio rerum); 2) наем услуг (locatio-conductio operarum); 3) наем работы или подряд (locatio-conductio opens или opens faciendi).
79082. Договор поручения. Содержание. Особенности правоотношений, возникающих из договора поручения. Прекращение договора поручения 25.5 KB
  Особенности правоотношений возникающих из договора поручения. Прекращение договора поручения. Договор поручения состоял в том что одно лицо дозритель мандант поручало а другое лицо мандатарий поверенный принимало на себя исполнение безвозмездно какихлибо действий.
79083. Договор товарищества. Виды товарищества. Права и обязанности товарищей в отношении друг друга и в отношении третьих лиц. Вклады. Участие в прибылях и убытках. Прекращение товарищества 26.64 KB
  Виды товарищества. Прекращение товарищества. Договором товарищества societs назывался договор по которому два лица или несколько лиц объединялись для достижения какойто общей хозяйственной цели разумеется не противоречащей праву.
79084. Зарождение юридических лиц. Статус корпораций, муниципий, фиска, благотворительных учреждений. Порядок возникновения юридических лиц. Основания прекращения юридических лиц 22.12 KB
  В древнереспубликанском праве еще не было имущества корпорации это была общая собственность членов корпорации но только неделимая пока существовала корпорация. В случае прекращения корпорации имущество делилось между последним составом ее членов. Наконец третий юрист Ульпиан3 говорил что в корпоративном объединении universits не имеет значения для бытия объединения остаются ли в нем все время одни и те же члены или только часть прежних или все заменены новыми; долги объединения не являются долгами отдельных его членов и права...
79085. Защита права собственности. Иски. Ответственность добросовестного и недобросовестного владельца перед собственником. Прекращение права собственности 20.82 KB
  Этот иск представлялся собственнику для истребования вещи владение которой им утрачено. Таким образом сторонами в виндикационном процессе являлись: в качестве истца собственник не имеющий фактического владения вещью; в качестве ответчика фактический обладатель вещи как держатель так и владелец ее притом владелец как недобросовестный так и добросовестный. Добросовестный владелец отвечал за состояние вещи со времени предъявления иска. вещи регулярно получаемые от другой плодоприносящей вещи при нормальном хозяйственном ее...
79086. Имущественные отношения супругов. Институт приданого. Основания прекращения брака. Конкубинат 21.11 KB
  Но принцип главенства мужа и подчинения жены проводился последовательно в течение всего того времени пока существовала практика браков cum mnu. Жена получала имя и сословное положение мужа; местожительство муха было обязательным местожительством и для жены; муж мог исковым порядком истребовать жену от всякого третьего лица у которого она находилась и т. при этом последствия нарушения верности были гораздо тяжелее для жены чем для мужа. При браке cum mnu все имущество жены поступало в полную собственность мужа сливаясь нераздельно с...
79087. Институты публичного права и изменения полномочий императора, сената и магистратуры в период домината (поздней империи) 21.7 KB
  начинается новый этап истории империи доминат во время которого Рим превратился в монархическое государство с абсолютной властью императора. Население империи превратилось из граждан в подданных императора которые стали рассматриваться даже как его рабы сервы. Большое значение для дальнейших судеб империи имели реформы Диоклетиана закрепленные и развитые в законодательстве Константина.