2020-04-07
82
1. Что такое граф? Приведите пример. Назовите известные вам типы графов.
2. В чем состоит различие между ориентированными и неориентированными графами?
3. Опишите известные вам способы задания графов.
4. Что называется подграфом и суграфом графа?
5. Что называется дополнением графа?
6. Какой граф называется двойственным?
7. Какие операции могут выполняться над графами?
8. Что такое мультиграф и как определяется его мультичисло?
9. Дайте определение регулярного графа.
10. Дайте определение нечеткого графа. В чем состоит отличие нечеткого неориентированного графа первого и второго рода?
ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ
1. Приведите примеры задания графа различными способами: аналитическим, графическим, матричным.
2. Задайте графическим и матричным способами ориентированный, неориентированный и смешанный граф.
3. Задайте произвольный граф G = (X, U), |X| = 9, |U| = 24 и запишите для него матрицу смежности и инцидентности, а также его списковое представление.
4. Приведите словесный описания и составьте структурную схему алгоритма перехода от матрицы инцидентности к матрице смежности и наоборот.
|
|
|
5. Определите количество ре бер в полном графе K15 без петель.
6. Постройте Платоновы графы.
7. Задайте Платоновы графы на основе матриц смежности и инцидентности.
8. Задан произвольный граф G = (X, U), где ½X½=6; ½U½=10. Постройте двойственный ему граф GS.
9. Приведите пример мультиграфа и определите его мультичисло.
10. Приведите примеры нечетких неориентированных графов первого и второго рода.
Понятие графа опирается на понятие множества. Графом можно назвать объект, состоящий из двух множеств: точек и линий, которые находятся между собой в некотором отношении. Множество точек графа обозначается X = { x 1, x 2, …, x n} и называется множеством вершин. Множество линий, соединяющих любые пары вершин (xi, xj) Î X, называется множеством ребер или дуг и обозначается U = { u 1, u 2, …, u m}.
