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


 

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

10906. Анализ использования трудовых ресурсов на предприятии (на примере ОАО «Саханефтегазсбыт») 75.07 KB
  Трудовые ресурсы – главная производительная сила общества, включающая трудоспособную часть населения страны, которая благодаря своим психофизиологическим и интеллектуальным качествам способна участвовать в общественно-полезной деятельности, производя материальные и духовные блага и услуги.
10907. Конструкційні матеріали і їх вибір. Види конструкційних матеріалів 46.5 KB
  Тема 6: Конструкційні матеріали і їх вибір. Види конструкційних матеріалів. Мета: Навчальна: сформувати знання вміння та навички розрізняти різноманітні матеріли. Виховна: виховувати в учнів бережливе ставлення та раціональне використання матеріалів. Розвиваюча:...
10908. Устройства отображения информации 170.7 KB
  В электронно-лучевых приборах создается тонкий пучок электронов (луч), который управляется электрическим или магнитным полем либо обоими полями. К этим приборам относятся электронно-лучевые трубки индикаторных устройств радиолокаторов, для осциллографии, приема телевизионных изображений (кинескопы),
10909. Технологія робіт лобзиком. Правила безпеки при роботі лобзиком. Організація робочого місця. Тематичне оцінювання. (усне опитування) 564 KB
  ТЕМА УРОКУ: Технологія робіт лобзиком. Правила безпеки при роботі лобзиком. Організація робочого місця. Тематичне оцінювання. усне опитування ЗМІСТ УРОКУ: Прийоми випилювання. Кріплення пилочки лобзика з використанням пристосувань за наявності. Способи випилювання. ...
10910. Технологія робіт лобзиком. Правила безпеки при роботі лобзиком. Організація робочого місця 107 KB
  Тема уроку: Технологія робіт лобзиком. Правила безпеки при роботі лобзиком. Організація робочого місця. Тематичне оцінювання. усне опитування Мета уроку. Формування вмінь виконувати пиляння фанери лобзиком; закріплення знань про пиляння деревини. Розвивати точність о...
10911. Методика проектного навчання на уроках технічної праці в 5 класі 987 KB
  Методика проектного навчання на уроках технічної праці в 5 класі 2.2.1 Проектування виробів Урок 1. Вступне заняття. Технологія як перетворююча діяльність людини 1 год. Мета уроку. Засвоєння знань про техніку технології основні види технологічної діяльності пр...
10912. Конструкційне макетування 44.5 KB
  Тема 1.4: Констукційні . Мета: Навчальна: сформувати знання вміння та навички повязані з макетуванням. Виховна: виховувати в учнів естетичне сприймання предметів культуру праці та бережливе ставлення до чужої праці. Розвиваюча: розвивати у школярів спеціальні
10913. Стандарт і якість. Ергономіка та біоніка 35.5 KB
  Тема 10:Стандарт і якість. Ергономіка та біоніка. Мета: Навчальна: сформувати знання вміння та навички повязані з даними поняттями. Виховна: виховувати в учнів культуру праці та бережливе ставлення до чужої праці. Естетичне сприймання предметів. Розвиваюча: розви...
10914. Промислова графіка. Умовні знаки, упаковка, реклама їх призначення види застосування 30 KB
  Тема 11: Промислова графіка. Умовні знаки упаковка реклама їх призначення види застосування. Мета: Навчальна: сформувати знання вміння та навички повязані з даними поняттями. Виховна: виховувати в учнів культуру праці та бережливе ставлення до чужої праці. Естет