ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 8622
Скачиваний: 22
161
X={1, 2, 3, 4, 5, 6, 7}, U={(1,4), (2,7), (3,6), (2,3), (1,3), (2,5),
(4,6), (3,4), (5,6), (2,7), (3,7),(6,7),(1,5)}.
Нарисуйте
его
,
двойственный
ему
граф
,
постройте
граф
,
изоморфный
исходному
,
матрицу
расстояний
,
задайте
списком
смежности
.
2.
Задан
граф
G=(X,U), X={x1,x2,x3,x4,x5}, U={(x1,x2),
(x1,x3), (x2,x3), (x2,x4), (x3,x4), (x3,x5),(x4,x4),(x4,x5)}.
Постро
-
ить
его
графическое
представление
и
матрицы
инциденций
и
смежности
,
все
простые
цепи
и
циклы
.
3.
Постройте
граф
G=(X,U), |X| =n, |U|=m. n=7, m=13.
Задай
-
те
его
с
помощью
матриц
смежности
и
инциденций
.
Постройте
схему
алгоритма
перехода
от
одной
матрицы
к
другой
.
Вариант №5
1.
Задан
граф
G=(X,U),
X={1, 2, 3, 4, 5, 6, 7, 8, 9}, U={(1,4), (1,8), (2,7), (3,6), (2,3),
(1,3), (2,5), (6,8), (5,6), (1,9), (9,3), (2,7), (7,7), (3,7)}.
2.
Нарисуйте
его
,
двойственный
ему
граф
,
дайте
полную
характеристику
(
связность
,
циклы
,
ориентированность
,
матрица
расстояний
и
т
.
д
.),
задайте
матрицей
смежности
.
Задан
граф
G=(X,U), X={x1,x2,x3,x4,x5},U={(x1,x2), (x1,x3),
(x2,x3), (x2,x4), (x3,x4), (x3,x5),(x4,x4),(x4,x5)}.
Построить
его
графическое
представление
и
матрицы
инциденций
и
смежности
,
все
простые
цепи
и
циклы
.
3.
Подсчитайте
число
суграфов
,
включая
изоморфные
,
в
графе
G=(X,U), |X| =n.
Вариант №6
1.
Задан
граф
G=(X,U),
X={1, 2, 3, 4, 5, 6, 7, 8, 9}, U={(1,4), (1,8), (2,7), (3,6), (2,3),
(1,3), (2,5), (6,8), (5,6), (1,9), (9,3), (2,7), (7,7), (3,7)}.
2.
Нарисуйте
его
,
двойственный
ему
граф
,
найдите
подграф
,
суграф
,
дополненние
до
полного
графа
,
постройте
матрицу
рас
-
стояний
,
определите
диаметр
графа
.
Задан
граф
G=(X,U), X={x1,x2,x3,x4,x6,x6}, U={(x4,x1),
(x1,x2), (x2,x6), (x6,x5),(x2,x3),(x3,x5),(x5,x2)}.
Построить
рас
-
краску
графа
и
найти
его
хроматическое
число
.
162
3.
Подсчитайте
число
суграфов
,
включая
изоморфные
,
в
графе
G=(X,U), |X| =n.
Вариант №7
1.
Задан
граф
G=(X,U),
X={1, 2, 3, 4, 5, 6, 7}, U={(1,4), (2,7), (3,6), (2,3), (1,3), (2,5),
(4,6), (3,4), (5,6), (2,7), (3,7),(6,7),(1,5)}.
Нарисуйте
его
,
двойственный
ему
граф
,
задайте
матрицей
инциденций
,
постройте
подграф
,
суграф
,
дополнение
до
полного
графа
,
определите
диаметр
графа
и
его
хроматическое
число
.
2.
Задан
граф
G=(X,U), X={x1,x2,x3,x4,x5,x6}, U={(x1,x2),
(x2,x4), (x4,x3), (x1,x1), (x3,x6), (x3,x2), (x1,x5), (x3,x1), (x6,x5),
(x6,x1), (x3,x5), (x5,x4)}.
Постройте
граф
.
Найдите
минимальное
покрывающее
его
дерево
.
Вес
вершин
2,6,4,2,5,4,7,9,2,4,6,4
соот
-
ветственно
.
3.
Предложите
методы
построения
графов
с
эйлеровыми
и
гамильтоновыми
циклами
на
заданных
наборах
вершин
и
ребер
.
Вариант №8
1.
Задан
граф
G=(X,U),
X={1, 2, 3, 4, 5, 6, 7, 8, 9}, U={(2,4), (2,8), (2,7), (3,6), (2,3),
(1,3), (2,5), (4,6), (5,6), (4,8), (1,9), (9,3), (1,7), (7,4), (3,7)}.
2.
Нарисуйте
его
,
двойственный
ему
граф
,
задайте
матрицей
инциденций
,
смежности
,
найдите
эйлеров
цикл
,
гамильтонов
цикл
,
постройте
плоский
и
планарный
граф
.
Задан
граф
G=(X,U), X={x1,x2,x3,x4,x5}, U={(x1,x2),
(x2,x4), (x4,x3), (x1,x1), (x3,x4), (x3,x2), (x1,x5), (x3,x1), (x5,x5),
(x2,x1), (x3,x5), (x5,x4)}.
Постройте
его
,
найдите
все
простые
це
-
пи
.
3.
Предложите
алгоритм
построения
двудольных
графов
с
заданным
числом
вершин
.
Вариант №9
1.
Задан
граф
G=(X,U),
X={1,2,3,4,5}, U={(1,3),(2,4),(5,1)(3,5),(5,4)(1,4)}.
Нарисуйте
его
,
задайте
матрицу
смежности
и
инциденций
,
нарисуйте
двойственный
ему
граф
и
для
него
задайте
матрицы
163
смежности
и
инциденций
,
найдите
диаметр
графа
и
его
хромати
-
ческое
число
.
2.
Задан
граф
G=(X,U), X={x1,x2,x3,x4,x5}, U={(x1,x2),
(x2,x4), (x4,x3), (x1,x1), (x3,x4), (x3,x2), (x1,x5), (x3,x1), (x5,x5),
(x2,x1), (x3,x5), (x5,x4)}.
Построить
граф
.
Найдите
минимальное
покрывающее
его
дерево
.
Вес
вершин
2,1,4,2,7,4,7,3,2,4,6,4
соот
-
ветственно
.
3.
Определите
хроматическое
число
неполного
связного
графа
G=(X,U), |X| =n, |U|=m. n=8, m=18.
Вариант №10
1.
Задан
граф
G=(X,U),
X={1,2,3,4,5}, U={(1,3),(2,4),(2,1)(3,5),(5,4)(1,4),(4,4)}.
Нарисуйте
его
,
задайте
матрицу
смежности
и
инциденций
,
нарисуйте
двойственный
ему
граф
и
для
него
задайте
матрицы
смежности
и
инциденций
,
постройте
плоский
и
планарный
граф
.
2.
Дайте
определение
Эйлерова
графа
.
Приведите
пример
.
Будет
ли
граф
G=(X,U), X={x1,x2,x3,x4,x5}, U={(x1,x2), (x2,x3),
(x2,x5), (x3,x4), (x1,x4), (x3,x5)}
Эйлеровым
?
Нарисуйте
его
.
По
-
стройте
минимальный
цикл
.
3.
Постройте
произвольный
граф
G=(X,U), |X| =n, |U|=m.
n=10, m=18.
Определите
его
цикломатическое
число
.
Укажите
,
какие
ребра
должны
быть
удалены
из
графа
,
чтобы
он
стал
ацик
-
лическим
.
Вариант №11
1.
Задан
граф
G=(X,U),
X={1,2,3,4,5,6}, U={(1,3),(2,4),(5,1)(3,5),(5,4)(1,4),(6,3)}.
Нарисуйте
его
,
задайте
матрицу
смежности
и
инциденций
,
нарисуйте
двойственный
ему
граф
и
для
него
задайте
матрицы
смежности
и
инциденций
,
нарисуйте
изоморфный
ему
граф
,
оп
-
ределите
его
диаметр
.
2.
Задан
граф
.
Найдите
минимальное
покрывающее
его
де
-
рево
. G=(X,U), X={x1,x2,x3,x4,x5,x6,x7},
U={(x1,x3)(x1,x2)(x1,x4)(x2,x3)(x2,x6)(x2,x5)(x3,x4)(x3,x7)(x4,x5)
(x4,x6)(x1,x6)(x7,x6)}. «
Вес
»
ребер
равен
: 4,3,1,6,1,4,5,2,7,8,1,9
соответственно
.
164
3.
Определите
множество
полных
графов
,
содержащих
од
-
новременно
эйлеровы
и
гамильтоновы
циклы
.
Вариант №12
1.
Задан
граф
G=(X,U),
X={1,2,3,4,5}, U={(2,4),(5,1)(3,5),(5,5)(1,4)}.
Нарисуйте
его
,
задайте
матрицу
смежности
и
инциденций
,
нарисуйте
двойственный
ему
граф
и
для
него
задайте
матрицы
смежности
и
инциденций
.
Для
исходного
графа
нарисуйте
планарный
и
плоский
граф
,
определите
его
хроматическое
число
.
2.
Задан
граф
G=(X,U), X={x1,x2,x3,x4}, U={(x1,x2), (x1,x3),
(x2,x3), (x2,x4), (x3,x4), (x1,x4),(x4,x4)}.
Построить
все
простые
цепи
из
Х
1
в
Х
3.
3.
Доказать
,
что
среди
любых
6
человек
есть
либо
3
попарно
знакомых
,
либо
3
попарно
незнакомых
.
Вариант №13
1.
Задан
граф
G=(X,U),
X={1,2,3,4,5}, U={(1,3),(3,4),(5,2)(3,5),(5,4)(1,4)}.
Нарисуйте
его
,
задайте
матрицу
смежности
и
инциденций
,
нарисуйте
двойственный
ему
граф
и
для
него
задайте
матрицы
смежности
и
инциденций
.
2.
Задан
граф
G=(X,U), X={x1,x2,x3,x4,x5}, U={(x1,x2),
(x1,x3), (x2,x3), (x2,x4), (x3,x4), (x3,x5),(x4,x4),(x4,x5)}.
Постро
-
ить
его
графическое
представление
,
все
простые
цепи
и
циклы
.
3.
Описать
в
терминах
теории
графов
отношение
эквива
-
лентности
на
конечном
множестве
.
Вариант №14
1.
Задан
граф
G=(X,U),
X={1, 2, 3, 4, 5, 6, 7, 8, 9}, U={(2,4), <2,8>, <2,7>, <3,6>,
(2,3), (1,3), (2,5), (4,6), (5,6), <4,8>, <1,9>, <9,3>, (1,7), (2,5), (7,4),
(3,7), <7,2>, <8,3>, <3,6>}.
Нарисуйте
его
,
дайте
полную
характеристику
.
2.
Задан
граф
G=(X,U), X={x1,x2,x3,x4,x6,x5}, U={(x1,x2),
(x2,x4), (x4,x3), (x1,x1), (x3,x5), (x3,x2), (x1,x5), (x3,x1), (x2,x5),
(x6,x1), (x3,x5), (x5,x4)}.
Дайте
определения
:
маршрута
,
цепи
,
165
цикла
,
связности
.
Постройте
на
заданном
графе
маршрут
,
цепь
,
цикл
,
покрывающее
его
дерево
.
3.
Доказать
,
что
если
граф
связен
и
конечен
,
то
поиск
в
ши
-
рину
и
поиск
в
глубину
обойдут
все
его
вершины
по
одному
разу
.
Вариант №15
1.
Задан
граф
G=(X,U),
X={1, 2, 3, 4, 5, 6}, U={(2,4), (2,5), (4,6), (5,6), (2,5),
(6,1),(3,6).(2,1),(1,1)}
Нарисуйте
его
,
дайте
полную
характери
-
стику
, (
связность
,
ориентированность
,
матрица
расстояний
,
хро
-
матическое
число
,
планарность
и
т
.
д
.).
2.
Дайте
определение
Эйлерова
графа
.
Приведите
пример
.
Будет
ли
граф
G=(X,U), X={x1,x2,x3,x4,x5}, U={(x1,x2), (x1,x3),
(x1,x2), (x2,x4), (x3,x4), (x3,x5) (
х
2,
х
5)}
Эйлеровым
?
Нарисуйте
его
.
Постройте
минимальный
цикл
.
3.
Доказать
,
что
граф
связен
тогда
и
только
тогда
,
когда
его
нельзя
представить
в
виде
объединения
двух
графов
.
Вариант №16
1.
Задан
граф
G=(X,U),
X={1, 2, 3, 4, 5, 6, 7, 8, 9}, U={(2,4), (2,8), (2,7), (3,6), (2,3),
(1,3), (2,5), (4,6), (5,6), (4,8), (1,9), (9,3), (1,7), (2,5), (7,4), (3,7)}.
Нарисуйте
его
,
дайте
полную
характеристику
, (
связность
,
циклы
,
ориентированность
,
матрица
расстояний
и
т
.
д
.)
задайте
матрицей
смежности
.
2.
Задан
граф
G=(X,U), X={x1,x2,x3,x4,
х
5}, U={(x1,x2),
(x1,x3),(x2,x3),(x2,x4),(x3,x4),(x1,x4),(x4,x4),(
х
3,
х
5),(
х
5,
х
4),(
х
1,
х
5)}.
Построить
все
простые
цепи
из
Х
2
в
Х
5.
3.
Нарисовать
диаграммы
всех
деревьев
с
7
вершинами
.
Вариант №17
1.
Задан
граф
G=(X,U),
X={1, 2, 3, 4, 5, 6, 7, 8, 9}, U={(1,4), (1,8), (2,7), (3,6), (2,3),
(1,3), (2,5), (4,6), (3,4), (6,8), (5,6), (4,8), (1,9), (9,3), (2,7), (7,6),
(4,3), (2,5), (7,7), (3,7)}.
Нарисуйте
его
,
дайте
полную
характеристику
(
связность
,
циклы
,
ориентированность
,
матрица
расстояний
и
т
.
д
.),
задайте
матрицей
смежности
.