Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

Числовые характеристики графов. Хроматическое число графов кратко

Лекция



Привет, сегодня поговорим про числовые характеристики графов, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое числовые характеристики графов, хроматическое число графов, хроматическое число, реберная раскраска, хроматический многочлен , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..

хроматическое число графа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обозначается χ(G).

Определение

Хроматическое число графа — минимальное число Числовые характеристики графов. Хроматическое число графов, такое что множество Числовые характеристики графов. Хроматическое число графов вершин графа можно разбить на Числовые характеристики графов. Хроматическое число графов непересекающихся классов Числовые характеристики графов. Хроматическое число графов:

Числовые характеристики графов. Хроматическое число графов

таких, что вершины в каждом классе независимы, то есть любое ребро графа не соединяет вершины одного и того же класса.

Связанные определения

  • K-раскрашиваемый граф — граф, хроматическое число которого не превосходит Числовые характеристики графов. Хроматическое число графов. То есть его вершины можно раскрасить Числовые характеристики графов. Хроматическое число графов разными цветами так, что у любого ребра концы будут разного цвета.
  • K-хроматический граф — граф, хроматическое число которого равно Числовые характеристики графов. Хроматическое число графов. То есть вершины графа можно раскрасить Числовые характеристики графов. Хроматическое число графов цветами так, что у любого ребра концы будут разного цвета, но так раскрасить Числовые характеристики графов. Хроматическое число графов цветами — уже нельзя.

Раскраска вершин

Числовые характеристики графов. Хроматическое число графов

Этот граф может быть раскрашен 3 цветами 12 способами.

Когда говорят о раскраске графов, почти всегда подразумевают под этим раскраску их вершин, то есть присвоение цветовых меток вершинам графа так, чтобы любые две вершины, имеющие общее ребро, имели разные цвета. Так как графы, в которых есть петли, не могут быть раскрашены таким образом, они не являются предметом обсуждения.

Терминология, в которой метки называются цветами, происходит от раскраски политических карт. Такие метки как красный или синий используются, только когда число цветов мало, обычно же подразумевается, что метки являются целыми числами Числовые характеристики графов. Хроматическое число графов.

Раскраска с использованием Числовые характеристики графов. Хроматическое число графов цветов называется Числовые характеристики графов. Хроматическое число графов-раскраской. Наименьшее число цветов, необходимое для раскраски графа Числовые характеристики графов. Хроматическое число графов, называется его хроматическим числом и часто записывается как Числовые характеристики графов. Хроматическое число графов. Иногда используется Числовые характеристики графов. Хроматическое число графов, с тех пор как Числовые характеристики графов. Хроматическое число графов обозначает Эйлерову характеристику. Подмножество вершин, выделенных одним цветом, называется цветовым классом, каждый такой класс формирует независимый набор. Таким образом, Числовые характеристики графов. Хроматическое число графов-раскраска — это то же самое, что и разделение вершин на {\displaystyle k}Числовые характеристики графов. Хроматическое число графов независимых наборов[1].

Числовые характеристики графов. Хроматическое число графов

Корректная раскраска вершин графа Петерсена наименьшим набором цветов — тремя.

реберная раскраска

Числовые характеристики графов. Хроматическое число графов

реберная раскраска кубического графа Дезарга.

Хроматический класс графа G — минимальное число цветов, в которые можно раскрасить ребра графа G так, чтобы смежные ребра имели разные цвета. Об этом говорит сайт https://intellect.icu . Обозначается χ'(G). Проблема реберной раскраски произвольного плоского кубического графа без мостов тремя цветами эквивалентна знаменитой Проблеме четырех красок. Реберная раскраска определяет 1-факторизацию графа.

хроматический многочлен

Если рассмотреть количество различных раскрасок помеченного графа как функцию от доступного числа цветов t, то оказывается, что эта функция всегда будет полиномом от t. Этот факт был обнаруженБиркгофом и Льюисом [1] при попытке доказать гипотезу четырех красок.

Хроматические многочлены некоторых графов

Треугольник Числовые характеристики графов. Хроматическое число графов Числовые характеристики графов. Хроматическое число графов
Полный граф Числовые характеристики графов. Хроматическое число графов Числовые характеристики графов. Хроматическое число графов
Дерево с Числовые характеристики графов. Хроматическое число графоввершинами Числовые характеристики графов. Хроматическое число графов
Цикл Числовые характеристики графов. Хроматическое число графов Числовые характеристики графов. Хроматическое число графов
Граф Петерсена Числовые характеристики графов. Хроматическое число графов

Нахождение хроматического многочлена произвольного графа[править ]

Для графа-вершины хроматический многочлен равен Числовые характеристики графов. Хроматическое число графов

Числовые характеристики графов. Хроматическое число графов

Хроматический многочлен графа равен произведению хроматических многочленов его компонент

Числовые характеристики графов. Хроматическое число графов

Также существует рекуррентное соотношение

Числовые характеристики графов. Хроматическое число графов

где Числовые характеристики графов. Хроматическое число графов и Числовые характеристики графов. Хроматическое число графов — смежные вершины, Числовые характеристики графов. Хроматическое число графов — граф, получающийся из графа Числовые характеристики графов. Хроматическое число графов путем удаления ребра Числовые характеристики графов. Хроматическое число графов а Числовые характеристики графов. Хроматическое число графов — граф, получающийся из графа Числовые характеристики графов. Хроматическое число графов путем стягивания ребра Числовые характеристики графов. Хроматическое число графов в точку.
Можно использовать эквивалентную формулу

Числовые характеристики графов. Хроматическое число графов

где Числовые характеристики графов. Хроматическое число графов и Числовые характеристики графов. Хроматическое число графов — несмежные вершины, а Числовые характеристики графов. Хроматическое число графов — граф, получающийся из графа Числовые характеристики графов. Хроматическое число графов путем добавления ребра Числовые характеристики графов. Хроматическое число графов

Свойства хроматического многочлена[править ]

Для всех целых положительных Числовые характеристики графов. Хроматическое число графов

Числовые характеристики графов. Хроматическое число графов

Хроматическое число Числовые характеристики графов. Хроматическое число графов — наименьшее целое положительное Числовые характеристики графов. Хроматическое число графов, для которого

Числовые характеристики графов. Хроматическое число графов

Обобщения

Также хроматическое число можно рассматривать для других объектов, например, для метрических пространств. Так, хроматическим числом плоскости называется минимальное число цветов χ, для которого существует такая раскраска всех точек плоскости в один из цветов, что никакие две точки одного цвета не находятся на расстоянии ровно 1 друг от друга. Аналогично для любой размерности пространства. Элементарно доказывается, что для плоскости Числовые характеристики графов. Хроматическое число графов, однако продвинуться дальше до сих пор не удается. Эта задача называется проблемой Нелсона — Эрдеша — Хадвигера.

Значение для теории графов и практическое применение

Множество глубоких задач теории графов легко формулируются в терминах раскраски. Самая знаменитая из таких задач, проблема четырех красок, в настоящее время решена, однако появляются новые, например, обобщение проблемы четырех красок, гипотеза Хадвигера.

Планирование

Раскраска вершин моделирует многие проблемы планирования. В своей простейшей постановке заданный набор работ должен быть распределен по временным отрезкам, каждая такая работа занимает один отрезок. Они могут быть выполнены в любом порядке, но две работы могут конфликтовать в том смысле, что не могут быть выполнены одновременно, так как, например, используют общие ресурсы. Соответствующий граф содержит вершину для каждой из работ и ребро для каждой конфликтующий пары. Хроматическое число построенного графа — это минимальное время выполнения всех работ без конфликтов.

Детали проблемы планирования определяют структуру графа. Например, когда идет распределение самолетов по рейсам, результирующий граф конфликтов является интервальным графом, так что проблема раскраски может быть решена эффективно. При распределении радиочастот получается граф единичных кругов конфликтов, и для такой задачи существует 3-аппроксимационный алгоритм.

Распределение регистров

Компилятор — это компьютерная программа, которая переводит один компьютерный язык в другой. Для улучшения времени выполнения результирующего кода одной из техник компиляторной оптимизации, является распределение регистров, в которой наиболее часто используемые переменные компилируемой программы хранятся в быстродействующих регистрах процессора. В идеальном случае переменные хранятся в регистрах так, что они все находятся в регистрах во время их использования.

Стандартный подход к этой задаче состоит в сведении ее к задаче раскраски графов[8]. Компилятор строит интерференционный граф, где вершины соответствуют переменным, а грань соединяет две из них, если они нужны в один и тот же момент времени. Если этот граф k-хроматический, то переменные могут храниться в k регистрах.

Цифровые водяные знаки

Технология цифровых водяных знаков (англ. digital watermarking) позволяет вместе с данными (будь то медиафайлы, исполняемые файлы и прочие) передать некое скрытое сообщение («водяной знак», Watermark). Такое скрытое сообщение может быть применено в защите авторских прав для идентификации владельца данных.

Это важно, например, для установления источника их распространения нелегальным образом. Или же для подтверждения прав на данные, например — программное обеспечение систем на кристалле (system-on-chip).

Сообщение можно закодировать в том числе и в способе распределения регистров. Одну из таких техник предложили Qu и Potkonjak[37] (поэтому ее иногда называют QP-алгоритмом).

Состоит она вот в чем: пусть Числовые характеристики графов. Хроматическое число графов — граф несовместимости (интерференционный граф) распределения регистров процессора, о котором говорилось выше. Его раскраска используется в программе — причем, используется так, что допустимо поменять содержимое графа с небольшим увеличением его хроматического числа. Оказывается возможно закодировать послание в программном продукте с помощью раскраски графа Числовые характеристики графов. Хроматическое число графов, то есть распределения регистров.

Извлечь это сообщение можно путем сравнением распределения регистров с исходной раскраской;[38] существуют и способы удостовериться в том, было ли некое сообщение закодировано в программе без использования исходного.

В дальнейшем разные авторы развивали и уточняли идеи Qu и Potkonjak[39].[38][40]

Другие применения

Задача раскраски графов была поставлена во многих других областях применения, включая сопоставление с образцом.

Решение головоломки судоку можно рассматривать как завершение раскраски 9 цветами заданного графа из 81 вершины.

Вау!! 😲 Ты еще не читал? Это зря!

Примечания

  1. Birkhoff, G. D. and Lewis, D. C. «Chromatic Polynomials.» Trans. Amer. Math. Soc. 60, 355—451, 1946.

Литература

  • О. Оре. Теория графов . Перевод с английского И. Н. Врублевской, под редакцией Н. Н. Воробьева. М.: Наука , 1986.

На этом все! Теперь вы знаете все про числовые характеристики графов, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое числовые характеристики графов, хроматическое число графов, хроматическое число, реберная раскраска, хроматический многочлен и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика.

Из статьи мы узнали кратко, но содержательно про числовые характеристики графов
создано: 2014-11-01
обновлено: 2021-03-13
132960



Рейтиг 9 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Дискретная математика. Теория множеств . Теория графов . Комбинаторика.

Термины: Дискретная математика. Теория множеств . Теория графов . Комбинаторика.