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


 

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

9509. Иоганн Вольфганг Гете 1749 - 1832 Johann Wolfgang Goethe 31.13 KB
  5 Иоганн Вольфганг Гете 1749 - 1832 Johann Wolfgang Goethe Общечеловеческий гений (Гомер, Шекспир) Разносторонний: красавец, долгожитель, светский человек, государственный деятель, ученый-натуралист, поэт, драматург, прозаик + актер, художник Совре...
9510. Дени Дидро 1713 – 1784 50.29 KB
  Дени Дидро 1713 – 1784 Родился в семье ремесленника. Духовная карьера – не стал. С 20 лет – интеллигент, бедняк. Разносторонние таланты, в том числе, организаторский. (Энциклопедия) Дидро дважды попадал в тюрьму (в 1749 и в 1...
9511. Лирика Иоганна Вольфганга Гёте 81.96 KB
  36 Лирика Иоганна Вольфганга Гёте Когда мы говорим о творчестве Гете, мы непременно подчеркиваем замечательный универсализм художника, проявившийся в создании им прекрасных образцов драмы, эпической поэмы, романа. Но наиболее велик, непререкаемо пре...
9512. Поэмы Оссиана Джеймса Макферсона 240.86 KB
  Поэмы Оссиана Джеймса Макферсона Осенью 1759 г. в курортный городок на юге Шотландии Моффат прибыл Томас Грэм (Graham), сын шотландского помещика, который в дальнейшем ста...
9513. Поэма Орлеанская девственница 36.11 KB
  1735 опубл. 1755 творчески перерабатывается сам жанр комической эпопеи, расширяется сфера комического, изменяется его социально-критическая функция в соответствии с просветительскими идеологическими задачами ПАРОД...
9514. Жан-Жак Руссо (1712 – 1778) 48.5 KB
  Жан-Жак Руссо (1712 – 1778) Швейцарец - фр гений Сложен, противоречив (история жизни – в Исповеди, факты верны, а освещение) Из демократических низов (как и многие просветители 2-го этапа): сын часовщика - сирота, бродяга, самообраз...
9515. Лоренс Стерн (Laurence Sterne, 1713 - 1768) 30.22 KB
  Лоренс Стерн (Laurence Sterne, 1713 - 1768) родился на юге Ирландии в семье пехотного офицера. В детстве вместе с семьей ему приходилось постоянно переезжать с места на место, скитаясь по казармам. Когда будущему писателю было 18 лет, умер отец. Бла...
9516. История зарубежной литературы XVIII века 572.35 KB
  История зарубежной литературы XVIII века Глава 1 История зарубежной литературы XVIII века Учебник для филологических специальностей вузов Под редакцией Л. В. Сидорченко Учебник рассматривает важнейшие закономерности развития литературы эпохи Просвещ...
9517. Память як багаторівневе, поліструктурне явище 30.5 KB
  Сприймання та память. Псих.час та память. Сприймання в яких людина пізнає оточуючу дійсність зазавичай не зникають безслідно. Вони закріплюються, зберігаються та відтворюються надалі у формі впізнання предметів, що ми бачимо, спогадах. Змістовне спр...