Расчет числа внутренней устойчивости (G) графа G

Составим таблицу 6.2 отображений и несмежных вершин графа G. Анализ таблицы 6.2 показывает, что в столбце ┐H_i есть несмежные вершины. В этом случае построим таблицу 6.4 двухэлементных множеств из несмежных вершин, найдем им образ и ┐.

Таблица 6.4 - Таблица образов и ┐

{xi,xj}		┐
4,6	5,7	8,9
4,8	5,7,9	6,9
4,9	5,7,8
5,8	4,6,7,9
5,9	4,6,7,8
6,8	5,7,9
6,9	5,7,8

Поскольку не во всех строках столбца ┐таблицы 6.4 указаны знаки , сформируем таблицу 6.5 трехэлементных множеств {x_i,x_j,x_k} и найдем им образи ┐ .

Таблица 6.5 - Таблица образов и ┐

{xi,xj,xk}		┐
4,6,8	5,7,9
4,6,9	5,8,7

Поскольку во всех строках таблицы 5.5 указаны знаки процесс вычислений закончен и можно перейти к анализу таблицы 6.4 и таблицы 6.5.

По итогам анализа можно сформировать множество S ядер графа G, т.е.

S={{x₅,x₈},{x₅,x₄},{x₄,x₆,x_8,},{x₄,x₆,x₉}},

где S₁={x₅,x₈}, S₂={x₅,x₉}, S₃={x₄,x₆,x₈}, S₄={x₄x₆,x₆}.

Тогда

(G)={|S_i|}={||}|_i=1;4=3.

На этом расчеты числовых характеристик графа G закончены.

2 Решение задач

Тема: «Графы. Основные понятия. Способы задания. Части графа»

Задачи для решения в аудитории

1. На рис. изображены графы с четырьмя вершинами в каждом. Сравнить графы.

2. Задать различными способами графы , представленные на рисунке ниже. Вычислить степени и полустепени вершин.

3. Для графов из задачи 2 построить полный граф, пустой граф, частичный граф, суграф, подграф, остов графа. Являются ли графы планарными?

4. Пусть неориентированный и ориентированный графы и на рисунке ниже. задают отношение , т.е. и . Каковы свойства отношения?

Домашнее задание

1. Какие графы в задаче 10 являются деревьями? Какие графы в задаче 10 являются полными? Постройте остов для каждого графа из задачи10.

2. Построить мультиграф и полный граф для графов, заданных в задаче 5.

3. Изобразите неориентиованный, ориентированный и смешанный графы.

4. Определить степени и полустепени вершин для графов, заданных в задаче 5.

5. Задать графы множествами их вершин и ребер. Сравнить графы .

6. Равны ли графы на рисунке ниже. Задать графы множествами их вершин и ребер. Сравнить графы.

7. Определить дополнение графа , если: 1) граф - пятиугольник, 2) граф - треугольник.

8. Для графа на рисунке ниже построить: частичный граф, подграф и суграф.

9. Когда граф называется полностью заданным? Задайте граф в форме отображений.

10. Построить матрицы смежности и инциденции графов, изображенных на рисунке ниже. Чему равны степени вершин?

3 Задание

Задание на РГР формулируется следующим образом: «Найти основные числа графа G по данным, приведенным в таблице 6.6 для модели графа, представленной на рисунке 6.17: число вершин, число ребер, степени всех вершин, число компонент связности, цикломатическое число, хроматическое число, плотность и неплотность графа, числа внешней и внутренней устойчивости».

Рисунок 6.17 - Модель графа G

Таблица 6.6 - Данные для формирования графа G по вариантам

Таблица 6.6 - Продолжение

4 Содержание отчета

1) Условие задачи в соответствии с вариантом.

2) Определение числа вершин.

3) Определение числа ребер.

4) Определение степени всех вершин.

5) Определение числа компонент связности.

6) Определение цикломатического числа.

7) Определение хроматического числа.

8) Определение плотности и неплотность графа.

9) Определение числа внешней и внутренней устойчивости.