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


 

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

7313. Трудовий договір та особливості його складання 344.5 KB
  Трудовий договір § 1. Поняття трудового договору Право на працю є основним конституційним правом громадян України. Воно проголошене ст. 43 Конституції України, визнається за кожною людиною і становить собою можливість заробляти на життя працею, яку ...
7314. Колективний договір. Контроль за виконанням колективного договору і види відповідальності 106 KB
  Колективний договір План Поняття колективного договору. Колективні переговори по укладенню колективного договору. Порядок укладення колективного договору і його зміст. Контроль за виконанням колективного договору і види відповідальності ...
7315. Керування пам’яттю в ОС. Простий безперервний розподіл і розподіл з перекриттям. Розподіл пам’яті статичними й динамічними розділами 121.5 KB
  Тема: Керування памяттю в ОС. Простий безперервний розподіл і розподіл з перекриттям. Розподіл памяті статичними й динамічними розділами План Основна память. Вимоги до адрес, використовуваних у програмах...
7316. Процесуальні строки і витрати 40.16 KB
  Процесуальні строки і витрати ПЛАН: Вступ. Поняття процесуальних строків та їх значення у кримінальному процесі. Класифікація строків у кримінальному процесі. Порядок обчислення процесуальних строків. Поняття і види процесуальних в...
7317. Розв’язування систем лінійних алгебраїчних рівнянь над скінченними полями 184.63 KB
  Ю.Д. Жданова. Лекції з ВГПМ. М2 ТЧ обчислювальні алгоритми. Лекція № 7 10 Тема: Розв’язування систем лінійних алгебраїчних рівнянь над скінченними полями План лекції: Алгоритм знаходження всіх цілочислових розв’язків лінійного а...
7318. Організаційні та правові основи захисту населення під час воєнних дій. Правила поводження населення в конкретних НС 63.5 KB
  Тема: Організаційні та правові основи захисту населення під час воєнних дій. Правила поводження населення в конкретних НС. План: Основні положення міжнародного права з питань захисту людей. Правила поводження населення в конкретних НС. Ве...
7319. Взаємовідносини у колективі 97.5 KB
  Взаємовідносини у колективі План Прийняття групового рішення. Соціально - психологічний клімат колективу. Одним із показників успішної діяльності керівника організації (фірми, колективу) є рівень сформованості соціально-психологічно...
7320. Основи психокорекції. Курс лекцій 264.5 KB
  Психокорекційна практика як основна форма діяльності практичного психолога Поняття про психологічну корекцію. Мета і завдання психокорекції. Принципи психокорекційної роботи: принцип єдності діагностики і кор...
7321. Тістечка. Напівфабрикати для приготування тістечок 45.5 KB
  Тістечка. Напівфабрикати для приготування тістечок. Класифікація тістечок. Особливості технології приготування тістечок. Основні органолептичні показники. Санітарні правила при приготуванні та реалізації. Умови та термін зберігання...