Решение задач
Тема: «Графы. Основные понятия. Способы задания. Части графа»
Задачи для решения в аудитории
На рис. изображены графы
с
четырьмя вершинами в каждом. Сравнить
графы.
Задать различными способами графы
,
представленные на рисунке ниже. Вычислить
степени и полустепени вершин.
Для графов из задачи 2 построить полный граф, пустой граф, частичный граф, суграф, подграф, остов графа. Являются ли графы планарными?
Пусть неориентированный и ориентированный графы
и
на рисунке ниже. задают отношение
,
т.е.
и
.
Каковы свойства отношения?
Домашнее задание
Какие графы в задаче 10 являются деревьями? Какие графы в задаче 10 являются полными? Постройте остов для каждого графа из задачи10.
Построить мультиграф и полный граф для графов, заданных в задаче 5.
Изобразите неориентиованный, ориентированный и смешанный графы.
Определить степени и полустепени вершин для графов, заданных в задаче 5.
Задать графы
множествами их вершин и ребер. Сравнить
графы
.
Р
авны
ли графы
на
рисунке ниже. Задать графы
множествами их вершин и ребер. Сравнить
графы.
Определить дополнение
графа
,
если: 1) граф
- пятиугольник, 2) граф
-
треугольник.Д
ля
графа на рисунке ниже построить:
частичный граф, подграф и суграф.
Когда граф называется полностью заданным? Задайте граф в форме отображений.
Построить матрицы смежности и инциденции графов, изображенных на рисунке ниже. Чему равны степени вершин?
Задание
Задание на РГР формулируется следующим образом: «Найти основные числа графа G по данным, приведенным в таблице 6.6 для модели графа, представленной на рисунке 6.17: число вершин, число ребер, степени всех вершин, число компонент связности, цикломатическое число, хроматическое число, плотность и неплотность графа, числа внешней и внутренней устойчивости».
Рисунок 6.17 - Модель графа G
Таблица 6.6 - Данные для формирования графа G по вариантам
Номер варианта |
Удалить в модели графа вершины {i} |
Удалить в модели графа ребра {(i,j)} |
1 |
{1,2} |
{(4,7),(6,7),(7,8),(7,10),(10,11),(10,13)} |
2 |
{1,2} |
{(6,7),(7,10),(7,12),(10,11),(10,13),(11,12)} |
3 |
{1,2} |
{(6,7),(4,7),(4,8),(7,10),(10,11),(10,13)} |
4 |
{1,2} |
{(6,7),(7,10),(7,12),(8,12),(10,11),(10,13)} |
5 |
{1,2} |
{(4,8),(6,7),(7,8),(7,10),(10,11),(10,13)} |
6 |
{2,5} |
{(3,7),(4,7),(4,8),(4,9),(7,10),(7,11)} |
7 |
{2,5} |
{(3,7),(4,7),(4,8),(4,9),(7,12),(8,12)} |
8 |
{2,5} |
{(3,7),(4,7),(4,8),(4,9),(7,10),(10,11)} |
9 |
{2,5} |
{(3,7),(4,7),(4,8),(4,9),(7,12),(11,12)} |
10 |
{2,5} |
{(3,7),(4,7),(4,8),(4,9),(7,11),(10,11)} |
11 |
{5,10} |
{(2,7),(3,7),(7,11),(7,12),(8,12),(9,12)} |
12 |
{5,10} |
{(4,7),(4,8),(7,11),(7,12),(8,12),(9,12)} |
13 |
{5,10} |
{(2,3),(2,7),(7,11),(7,12),(8,12),(9,12)} |
14 |
{5,10} |
{(3,4),(4,7),(7,10),(7,12),(8,12),(9,12)} |
15 |
{5,10} |
{(2,3),(3,7),(7,10),(7,12),(8,12),(9,12)} |
Таблица 6.6 - Продолжение
Номер варианта |
Удалить в модели графа вершины {i} |
Удалить в модели графа ребра {(i,j)} |
16 |
{10,13} |
{(1,2),(2,3),(2,7),(6,7),(7,8),(7,12)} |
17 |
{10,13} |
{(1,2),(2,3),(2,7),(3,4),(4,7),(6,7)} |
18 |
{10,13} |
{(1,2),(2,3),(2,7),(6,7),(7,12),(8,12)} |
19 |
{10,13} |
{(1,2),(2,3),(2,7),(4,7),(4,8),(6,7)} |
20 |
{10,13} |
{(1,2),(2,3),(2,7),(6,7),(7,8),(8,12)} |
34 |
{1,4} |
{(6,10),(7,8),(7,10),(7,12),(11,12),(12,13)} |
35 |
{1,4} |
{(2,6),(6,7),(7,8),(7,12),(11,12),(12,13)} |
36 |
{12,13} |
{(1,4),(3,4),(4,7),(6,7),(7,8),(7,10)} |
37 |
{12,13} |
{(1,4),(2,3),(2,7),(3,4),(4,7),(7,8)} |
38 |
{12,13} |
{(1,4),(3,4),(4,7),(6,10),(7,8),(7,10)} |
39 |
{12,13} |
{(1,4),(2,6),(2,7),(3,4),(4,7),(7,8)} |
40 |
{12,13} |
{(1,4),(3,4),(4,7),(6,7),(6,10),(7,8)} |
41 |
{6,8} |
{(3,7),(5,10),(7,10),(7,11),(7,12),(9,12)} |
42 |
{6,8} |
{(2,3),(5,10),(7,10),(7,11),(7,12),(9,12)} |
43 |
{6,8} |
{(1,3),(5,10),(7,10),(7,11),(7,12),(9,12)} |
44 |
{6,8} |
{(3,4),(5,10),(7,10),(7,11),(7,12),(9,12)} |
45 |
{6,8} |
{(5,10),(7,10),(7,11),(7,12),(9,12),(11,13)} |
46 |
{3,11} |
{(1,2),(2,7),(4,8),(6,7),(7,10),(10,13)} |
47 |
{3,11} |
{(1,2),(2,7),(6,7),(7,8),(7,10),(10,13)} |
48 |
{3,11} |
{(1,2),(2,7),(6,7),(7,10),(8,12),(10,13)} |
49 |
{3,11} |
{(1,2),(2,7),(6,7),(7,10),(8,9),(10,13)} |
50 |
{3,11} |
{(1,2),(2,7),(5,6),(6,7),(7,10),(10,13)} |
51 |
{2,9} |
{(6,7),(7,10),(7,12),(10,11),(10,13),(11,12)} |
52 |
{2,9} |
{(6,7),(7,8),(7,10),(7,12),(10,11),(10,13)} |
53 |
{2,9} |
{(6,7),(7,8),(7,10),(10,11),(10,13),(11,13)} |
54 |
{2,9} |
{(3,4),(4,7),(6,7),(7,10),(10,11),(10,13)} |
55 |
{2,9} |
{(4,7),(6,7),(7,8),(7,10),(10,11),(10,13)} |
56 |
{9,10} |
{(1,2),(2,3),(2,7),(3,4),(4,7),(6,7)} |
57 |
{9,10} |
{(1,2),(2,3),(2,7),(4,7),(6,7),(7,8)} |
58 |
{9,10} |
{(1,2),(2,3),(2,7),(6,7),(7,8),(7,12)} |
59 |
{9,10} |
{(1,2),(2,3),(2,7),(6,7),(7,12),(11,12)} |
60 |
{9,10} |
{(1,2),(2,3),(2,7),(3,4),(6,7),(7,8)} |