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


 

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

15007. Ақиқаттан адасудың азабы 49 KB
  Ақиқаттан адасудың азабы Әнес САРАЙ Қазақстан Республикасы Мемлекеттік сыйлығының лауреаты. Шыңғыс Айтматовтың: €œАдам тұлға ретінде трагедиялық қобалжулар арқылы ашылады€ деп айтқаны бар. Шындығында өмір тану мен адам тану дегеніміз – осы екеуінің траг...
15008. Ақыт қажының Жиһаншаһ дастанындағы Шаһзада бейнесі 53.5 KB
  Таңғажайып Рымхан Е.А. Бөкетов атындағы Қарағанды мемлекеттік университетінің аспиранты АҚЫТ ҚАЖЫНЫҢ ЖИҺАНШАҺ ДАСТАНЫНДАҒЫ ШАҺЗАДА БЕЙНЕСІ Халық ақындарының шығармашылығындағы фольклорлық дәстүр мәселесін сөз еткенде ел аузында сақталып келген аңы...
15010. Ахмет Байтұрсынұлының Аққу, шортан, һәм шаян мысалы 69.54 KB
  Ахмет Байтұрсынұлы Аққу шортан һәм шаян мысалы. Ашық сабақ жоспары. Сабақтың тақырыбы: Ахмеn Байтұрсынұлы Аққу шортан Һәм шаян мысалы. Сабақтың мақсаты: а білімділік: Қазақ халқының бір тума ұлы Ахмет Байтұрсынұлының қазақ әдебиетін
15011. Алғашқы қазақ газеттерінің тарихы 39.5 KB
  Алғашқы шығарылған қазақ газеттерінің тарихы. Кез келген әдебиет бір күннің төңірегінде өрбитін немесе белгілі бір тарихи кезеңнің оқиғасын баяндайтын тар ұғымды дүние емес. Мәдениеті бай елдердің әдебиеті де қаз тұрып қалыптасқанша қоғамның дамуы секілді т
15012. Алпамыс батыр дастанының зерттелуі 560 KB
  УДК 398.22 574 А 61 АЛПАМЫС БАТЫР ЖЫРЫНЫЊ ЗЕРТТЕЛУІ А. Аманбаева А. Мќашева Тараз мемлекеттік педагогикалыќ институты Тараз қ. Батырлар жыры ќазақ ауыз әдебиетінің өте ертеден келе жатқан күрделі саласының бірі. Батырлар жыры бір ғасырдың ғана жемісі емес.Ол...
15013. Алпамыс батыр жырын оқыту және тәрбие жұмыстары 42.5 KB
  ӘОЖ 373.371.83 АЛПАМЫС БАТЫР ЖЫРЫН ОҚЫТУ АРҚЫЛЫ ТӘРБИЕ ЖҰМЫСТАРЫНЫҢ ҚҰЗЫРЕТТІЛІГІН АРТТЫРУ З.Д. Көшімбетова Қ.А. Яссауи атындағы Халықаралық қазақтүрік университеті Тараз институты Тараз қ. Алпамыс батыр жыры қазақ халқының ауыз әдебиетіне жатады және жыр...
15014. Арқалық батыр жырының нұсқалары 230.5 KB
  Тақырыптың өзектілігі. Қазақ халқының кез келген халықтың эпикалық қазынасынан кем түспейтін телегей-теңіз мол, әрі көркемдігі кемел, танымдық-тағылымдық мәні зор жырларының басым көпшілігі, әлі де болса
15015. Асан Қайғы туралы аңыздар 176.5 KB
  Ұлттың рухы бейнеленген мұра халықтың асыл қазыналарының бірі екендігін тәуелсіздік мұраты жолында жаңа экономикалық және саяси-әлеуметтік реформаларды қарқынды...