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


 

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

66545. Многопоточность. Межпроцессорные взаимодействия 49 KB
  Два дочерних процесса выполняют некоторые циклы работ, передавая после окончания очередного цикла через очереди сообщений родительскому процессу очередные четыре строки некоторого стихотворения, при этом первый процесс передает нечетные четверостишья, второй - четные.
66546. МНОГОПОТОЧНОСТЬ. МЕЖПРОЦЕССНЫЕ ВЗАИМОДЕЙСТВИЯ 64.6 KB
  Написать программу, создающую два потока, которые выполняются в одном адресном пространстве (в одном процессе). Их разделяемый ресурс - целочисленный массив, который содержит данные совместного использования. Потоки должны обрабатывать массив поочередно.
66547. Разработка и отладка алгоритмов и программ c использованием структур данных 87.42 KB
  Цель работы: Получить практические навыки в разработке алгоритмов и написании программ на языке С с использованием структур данных. Оборудование: IBM – совместимый компьютер, Система программирования QC 2.5.
66548. Электрические аппараты систем автоматического управления 2.5 MB
  К этой группе относятся реле и датчики. Если при плавном изменении входной регулируемой величины выходной сигнал аппарата изменяется скачком то мы имеем дело с реле. К ним относятся автоматические выключатели реле тока напряжения плавкие предохранители тепловые реле и пр.
66549. Решение граничных задач для ОДУ. Метод сеток для дифференциальных уравнений в частных производных 196.5 KB
  В прямоугольной области строится сеточная область из одинаковых ячеек и приближающая область. В каждом узле исходное уравнение заменяется конечно-разностным уравнением. Приближенные значения производных в каждом узле находятся по значениям искомой функции в соседних узлах.
66550. Исследование дополнительных режимов работы беспроводного оборудования с применением антенно-фидерного оборудования 52 KB
  Цель работы: исследовать зоны покрытия электромагнитных волн антенн и антенно-фидерное оборудование. I.Исследование штатной антенны точки доступа DWL-2100AP 1.Включаем точки доступа DWL-G132 и DWL-2100AP 2.Выбираем внешнюю или внутреннюю антенны у DWL-2100AP...
66551. ДОСЛІДЖЕННЯ ТРИФАЗНОГО ЕЛЕКТРИЧНОГО КОЛА ПРИ 3’ЄДНАННІ СПОЖИВАЧІВ ЗІРКОЮ 1.01 MB
  Дослідити і вивчити режими роботи та властивості трифазних електричних кіл при з’єднанні фаз споживачів зіркою з нейтральним проводом і без нього. Перевірити співвідношення між фазними і лінійними напругам та струмами.
66552. Нейро-нечіткі мережі для поданя і обробки знань 102.15 KB
  Нейрониі мережі, наприклад, є зручними для задач розпізнавання образів, але дуже незручні для пояснення, як вони таке розпізнавання здійснюють. Вони можуть автоматично здобувати знання, але процес їхнього навчання найчастіше відбувається досить повільно
66553. Діагностика ПК POST-картами 140 KB
  Мета: Навчитися проводити діагностику ПК за допомогою POSTкартами Одним з найпростіших і ефективніших способів діагностики стану материнських плат при технічному обслуговуванні і ремонті персональних комп'ютерів є використання результатів виконання спеціальної процедури...