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


 

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

8187. Возникновение воспитания как особого вида общественной деятельности 38.67 KB
  Возникновение воспитания как особого вида общественной деятельности Воспитание возникло вместе с появлением человеческого общества и существует на протяжении всей его истории, с самого начала выполняя общую функцию передачи от поколения к поколению ...
8188. Развитие христианской педагогической традиции в Византии 26.53 KB
  Развитие христианской педагогической традиции в Византии Византия образовалась как государство в 359 г. на территории Восточной Римской империи и была завоевана турками-османами в 1453 г. В период IV–V вв. в Византии в теории и практике воспита...
8189. Развитие русской педагогической мысли в XIX в 44.77 KB
  Развитие русской педагогической мысли в XIX в В XIX в. шел процесс становления отечественной педагогической науки, формирования различных педагогических направлений и теорий. Значительным в этот период оказался вклад общественной мысли в развитие пр...
8190. Развитие школы и педагогики в России после октябрьской революции (1917 г.) 35.85 KB
  Развитие школы и педагогики в России после октябрьской революции (1917 г.) Реформирование системы образования в первые годы советской власти История отечественной школы и педагогики советского периода оказалась крайне драматичной и противоречивой. Д...
8191. Понятие о дидактике и ее исследование в педагогике 25.93 KB
  Понятие о дидактике и ее исследование в педагогике В главе о сущности и общих закономерностях воспитания показано, что важнейшим его аспектом является овладение личностью той стороной общественного опыта, которая включает в себя знания, практические...
8192. Содержание образования и основные тенденции его формирования на современном этапе развития общества 20.86 KB
  Содержание образования и основные тенденции его формирования на современном этапе развития общества Под содержанием образования понимают совокупность знаний, умений и навыков, которые должны усвоить ученики. При этом ЗНАНИЯ - это результат...
8193. Принципы обучения 14.75 KB
  Принципы обучения По-латыни principium - основа, первоначало. В педагогике под принципами понимают систему базовых идей педагогического процесса.. Дидактические принципы можно рассматривать с трех сторон: Во-первых, это система требований к орг...
8194. Метод как многомерное явление 54.51 KB
  Метод как многомерное явление Поиск ответа на традиционный дидактический вопрос - как учить - выводит нас на категорию методов обучения. Без методов невозможно достичь поставленной цели, реализовать намеченное содержание, наполнить обучение познават...
8195. Формы организации обучения и их развитие в дидактике. урок как основная форма школьного обучения 22.81 KB
  Формы организации обучения и их развитие в дидактике. урок как основная форма школьного обучения 1. Понятие о формах организации (организационных формах) обучения. Соотношение между формами организации обучения и его методами Осуществление обучения ...