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


 

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

59667. Ясне-красне Купайло: Фольклорний вечір 46.5 KB
  Ведучий 1: Сьогодні ми хочемо розповісти про надзвичайно поетичне свято Івана Купала яке дійшло до нас ще з поганських часів. Ведучий 2: Купайло свято молодіжне саме звідси єднання молодих сердець на святі і оспівування в піснях хлопця і дівчини попарне стрибання через багаття.
59668. Свято закінчення початкової школи 49.5 KB
  Прийшла така вже пора Але не сумувати тут зібрались А пригадати як все починалось 1 клас Ведучі. Пісня Вчать у школі Ведучі. І виявилось ой нелегко Писати палички й гачки Каліграфія моя Веж мере замучила...
59669. Буду я природі другом 38 KB
  Природа дає все необхідне для життя людей, тварин, рослин — воду і повітря. Природа потребує постійної уваги, турботи. Ми повинні берегти природу, охороняти її багатства.
59670. Ми до тебе, казко, в гості завітали 47 KB
  І знову пісня радісно дзвенить І казка на екрані оживає. Сьогодні ми Казку сюди запросили Щоб бачити Казку слухать гуртом А Казка в завії десь там заблудила. Але Казка до нас прийде тоді коли ми покажемо як добре знаємо казки. Казка виходить на сцену.
59671. Найрозумніший. Конкурс 36 KB
  Хто знає відповідь той піднімає руку. Хто швидше підніме руку той отримує право відповіді. Хто з цих птахів не вміє літати а Кури; б Страуси; в Колібрі; 2. Хто має найдовший дзьоб а Чапля; б Гуска; в Лелека;
59672. Козацькі забави (для дитячого садка) 39 KB
  Дам подумать тільки трошки Звуть його КОТИГОРОШКО Вхід Котигорошка: Гей простелися дорого Біди всі обійди Мене до перемоги Славної доведи Хоч я з виду й невеличкий Але знає кожен: У двобої навіть Змія Я здолати зможу. Котигорошко ніби лякається:...
59673. Сценарій свята останнього дзвоника 42.5 KB
  На сьогоднішньому святі випускники з хвилюванням чекають останнього дзвоника в стінах рідної школи, бо саме сьогодні вони прощаються зі своїми щасливими дитячими шкільними роками.
59674. Посвята в козачата 40 KB
  Зал прикрашений рушниками, калиною, портретами гетьманів. Козаки (старші школярі) збираються на козацьку раду, Кошовий — учень обраний на цю посаду. Іде рада козаків.
59675. Cвято матері. Будь благословенна, нене 41 KB
  Будь благословенна нене Методичні порад до проведення Свята Матері в навчальних закладах Травень місяць Пречистої Діви Марії. До Матері Божої звертаються християни просячи заступництва і допомоги.