Расчет числа внутренней устойчивости (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 по вариантам

Номер варианта	Удалить в модели графа вершины { i }	Удалить в модели графа ребра {(i,j)}
	{1,2}	{(4,7),(6,7),(7,8),(7,10),(10,11),(10,13)}
	{1,2}	{(6,7),(7,10),(7,12),(10,11),(10,13),(11,12)}
	{1,2}	{(6,7),(4,7),(4,8),(7,10),(10,11),(10,13)}
	{1,2}	{(6,7),(7,10),(7,12),(8,12),(10,11),(10,13)}
	{1,2}	{(4,8),(6,7),(7,8),(7,10),(10,11),(10,13)}
	{2,5}	{(3,7),(4,7),(4,8),(4,9),(7,10),(7,11)}
	{2,5}	{(3,7),(4,7),(4,8),(4,9),(7,12),(8,12)}
	{2,5}	{(3,7),(4,7),(4,8),(4,9),(7,10),(10,11)}
	{2,5}	{(3,7),(4,7),(4,8),(4,9),(7,12),(11,12)}
	{2,5}	{(3,7),(4,7),(4,8),(4,9),(7,11),(10,11)}
	{5,10}	{(2,7),(3,7),(7,11),(7,12),(8,12),(9,12)}
	{5,10}	{(4,7),(4,8),(7,11),(7,12),(8,12),(9,12)}
	{5,10}	{(2,3),(2,7),(7,11),(7,12),(8,12),(9,12)}
	{5,10}	{(3,4),(4,7),(7,10),(7,12),(8,12),(9,12)}
	{5,10}	{(2,3),(3,7),(7,10),(7,12),(8,12),(9,12)}

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

Номер варианта	Удалить в модели графа вершины {i}	Удалить в модели графа ребра {(i,j)}
	{10,13}	{(1,2),(2,3),(2,7),(6,7),(7,8),(7,12)}
	{10,13}	{(1,2),(2,3),(2,7),(3,4),(4,7),(6,7)}
	{10,13}	{(1,2),(2,3),(2,7),(6,7),(7,12),(8,12)}
	{10,13}	{(1,2),(2,3),(2,7),(4,7),(4,8),(6,7)}
	{10,13}	{(1,2),(2,3),(2,7),(6,7),(7,8),(8,12)}
	{1,4}	{(6,10),(7,8),(7,10),(7,12),(11,12),(12,13)}
	{1,4}	{(2,6),(6,7),(7,8),(7,12),(11,12),(12,13)}
	{12,13}	{(1,4),(3,4),(4,7),(6,7),(7,8),(7,10)}
	{12,13}	{(1,4),(2,3),(2,7),(3,4),(4,7),(7,8)}
	{12,13}	{(1,4),(3,4),(4,7),(6,10),(7,8),(7,10)}
	{12,13}	{(1,4),(2,6),(2,7),(3,4),(4,7),(7,8)}
	{12,13}	{(1,4),(3,4),(4,7),(6,7),(6,10),(7,8)}
	{6,8}	{(3,7),(5,10),(7,10),(7,11),(7,12),(9,12)}
	{6,8}	{(2,3),(5,10),(7,10),(7,11),(7,12),(9,12)}
	{6,8}	{(1,3),(5,10),(7,10),(7,11),(7,12),(9,12)}
	{6,8}	{(3,4),(5,10),(7,10),(7,11),(7,12),(9,12)}
	{6,8}	{(5,10),(7,10),(7,11),(7,12),(9,12),(11,13)}
	{3,11}	{(1,2),(2,7),(4,8),(6,7),(7,10),(10,13)}
	{3,11}	{(1,2),(2,7),(6,7),(7,8),(7,10),(10,13)}
	{3,11}	{(1,2),(2,7),(6,7),(7,10),(8,12),(10,13)}
	{3,11}	{(1,2),(2,7),(6,7),(7,10),(8,9),(10,13)}
	{3,11}	{(1,2),(2,7),(5,6),(6,7),(7,10),(10,13)}
	{2,9}	{(6,7),(7,10),(7,12),(10,11),(10,13),(11,12)}
	{2,9}	{(6,7),(7,8),(7,10),(7,12),(10,11),(10,13)}
	{2,9}	{(6,7),(7,8),(7,10),(10,11),(10,13),(11,13)}
	{2,9}	{(3,4),(4,7),(6,7),(7,10),(10,11),(10,13)}
	{2,9}	{(4,7),(6,7),(7,8),(7,10),(10,11),(10,13)}
	{9,10}	{(1,2),(2,3),(2,7),(3,4),(4,7),(6,7)}
	{9,10}	{(1,2),(2,3),(2,7),(4,7),(6,7),(7,8)}
	{9,10}	{(1,2),(2,3),(2,7),(6,7),(7,8),(7,12)}
	{9,10}	{(1,2),(2,3),(2,7),(6,7),(7,12),(11,12)}
	{9,10}	{(1,2),(2,3),(2,7),(3,4),(6,7),(7,8)}

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2014-10-31