Элементы теории графов и их технические приложения - 17 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

17
Хроматическое число. Пусть р – натуральное число. Граф G называют р-
хроматическим, если его вершины можно раскрасить р различными цветами так,
чтобы никакие две смежные вершины не были раскрашены одинаково. Наименьшее
число р, при котором граф является р-хроматическим, называют хроматическим
числом графа и обозначают
γ (G).
Если
γ (G)=2, то граф называют бихроматическим. Необходимым и
достаточным условием бихроматичности графа является отсутствие в нем циклов
нечетной длины. Хроматическое число играет важную роль при решении задачи
наиболее экономичного использования ячеек памяти при программировании. За
исключением случая бихроматического графа, определение хроматического числа
представляет собой довольно трудную задачу.
Множество внутренней устойчивости. Множество S⊆ V графа G=(V, E)
называют внутренне устойчивым, если никакие две вершины из S несмежны, т.е.
для любых u, v
∈S имеет место (u, v)
∉
Е.
Множество внутренней устойчивости, содержащее наибольшее число
элементов, называют наибольшим внутренне устойчивым множеством, а число
элементов этого множества – числом внутренней устойчивости графа G.
Наибольшее внутреннее устойчивое множество играет важную роль в теории связи.
Множество внешней устойчивости. Множество Т ⊂ V графа G=(V,E)
называют внешне устойчивым, если любая вершина не принадлежащая Т, соединена
дугами с вершинами из Т. Множество внешней устойчивости, содержащее
наименьшее число элементов называют наименьшим внешне устойчивым
множеством, а число элементов этого множества – числом внешней устойчивости
графа G.
Пример. Задача о пяти ферзях.
Сколько ферзей достаточно расставить на шахматной доске так,
чтобы каждая
клетка доски находилась под ударом хотя бы одного из них? Эта задача сводится к
отысканию наименьшего внешне устойчивого множества в графе с 64 вершинами
(клетки доски), у которого (u, v)
∈
Т тогда и только тогда, когда клетки u и v
расположены на одной и той же горизонтали, вертикали или диагонали. Число
внешней устойчивости
β =5 для ферзей,
β
=8 для ладей,
β
=12 для коней,
β
=8 для
слонов. Задача о восьми ферзях, которые нужно расставить на шахматной доске так,
чтобы ни один из них не находился под ударом другого, сводится к нахождению
наибольшего внутренне устойчивого множества, графа из предыдущей задачи.
Существуют алгоритмы нахождения внутренне устойчивого множества и
наименьшего внешне устойчивого множества (см. К.Берж. Теория графов
и ее
применения. М. 1962).
5. Представление графов с помощью матриц.
Информация, содержащаяся в некотором графе, может быть представлена в
иной, алгебраической форме посредством матриц. Эта связь графа и матрицы имеет
важное значение при практическом приложении топологических методов к
математическому описанию сложных систем, так как позволяет перевести

Страницы