Вопросы к экзамену по курсу “Дискретная математика” (стр. 7 )

	1	2	3	4	5
	3	2	3	2	3

Радиус графа .

Множество центральных вершин, т. е. множество вершин, эксентриситет которых равен радиусу графа 2

.

Центр графа - подграф графа .

=

Покажем центр графа на исходном графе:

Диаметр графа .

Множество периферических вершин, т. е. множество вершин, эксентриситет которых равен диаметру  графа 3

.

Периферия  графа - подграф графа .

=

Покажем периферию  графа на исходном графе:

Пары антиподальных вершин и соответствующие диаметры графа:

8. Графы. Независимые множества и клики.

Определение 1. Пусть дан неориентированный граф . Подмножество его вершин называется независимым, если любые две вершины из множества не связаны ребром, т. е. не смежны. Независимое подмножество вершин называется максимальным независимым, если к нему нельзя добавить новых вершин с охранением независимости.

Пример 1. В следующем графе

Подмножество вершин является независимым. Но оно не является максимально независимым, так как его можно расширить до нового  независимого множества , которое уже будет максимальным, т. е. не расширяемым. В данном множестве имеется и другое независимое подмножество вершин , которое будет при этом максимальным независимым подмножеством вершин.

Обозначим через  совокупность всех максимальных независимых подмножеств неориентированного графа . Например, для графа из примера 1 имеем . Данная функция обладает следующими свойствами. Если граф пустой, т. е. , то , т. е. в пустом графе имеется одно максимальное независимое множество, состоящее из пустого множества вершин. Если множество всех изолированных вершин данного графа, то , т. е. все изолированные вершины данного графа присоединяются к максимальным независимых множествам остаточного графа , получаемого удалением всех изолированных вершин. Пусть граф не пустой и не имеет изолированных вершин. Для нахождения множества всех его независимых подмножеств организуется рекурсивный алгоритм построения дерева всех возможных вариантов. Ветвление в узлах дерева осуществляется следующим образом. Пусть узел дерева характеризуется уже отобранным множеством вершин , т. е. частичным независимым множеством вершин и остаточным графом служащим для расширения текущего независимого подмножества до максимального. Граф не пуст, иначе множество было бы максимальным, а вершина дерева вариантов была бы терминальной. Также остаточный граф не должен иметь изолированных вершин, так как они должны быть присоединены к множеству в процессе формирования узла . Возьмем вершину с наименьшей степенью. Если таких вершин несколько, для определенности, вершину с наименьшим номером. Пусть - окрестность вершины в графе , т. е. совокупность вершин, смежных с вершиной . Либо сама вершина , либо некоторая вершина должны добавляться в текущее независимое подмножество . Поэтому ветвление заключается в построении новых узлов дерева с параметрами и . Вспомним при этом, что каноническая операция удаления вершины из графа, это удаление этой вершины и всех смежных с ней. Если в графе при этом образуются изолированные вершины, они также удаляются и добавляются к новому текущему независимому подмножеству . Если полученное множество уже встречалось ранее на предыдущих этапах построения, узел в реальности не формируется, в противном случае узел добавляется в дерево вариантов со своими параметрами . Если остаточный граф =, т. е. пустой, то узел является терминальным (листом) и далее не ветвится. В этом случае множество является максимальным независимым подмножеством и добавляется к семейству всех максимальных независимых подмножеств данного графа, т. е. осуществляется присваивание .