Вопросы на зачет

Графы. Основные определения. Соотношения между количеством ребер и количеством вершин.

G=(V, E, I),

G – граф,

V – порядок (число вершин);

E – размер графа (число рёбер).

W – вес графа, символ(цифра) на ребре, записывается по порядку вершин

Степень вершины – количество рёбер выходящих их вершины

Простой граф - только одно ребро между вершинами и без петель. Проверяйте кол-во вершин степени вершины (невозможно при 4 вершинах иметь степень вершины больше 3-х)

входящая степень вершины 2 = 1, исходящая степень = 2

Простой граф – не имеет петель, а также если он не имеет рёбер с одинаковой упорядоченной парой вершин.

простой граф

Смежность вершин для неориентированного – вершина Y смежна с вершиной X, если в графе существует ребро соединяющее вершину Y с вершиной X.

Смежность вершин для ориентированного – вершина Y смежна с вершиной X, если в ориентированном графе существует ребро исходящее из вершины Х и входящее в вершину Y.

вершина Y смежная, Х несменная

матрица смежности

	1	2
1
2

Ориентирований граф матрица смежности, из 1 в 2

список смежности

турнир

Ответ:

Полный граф – каждая вершина соеденена с каждой вершиной

Однородный граф – это граф, степени всех вершин которого

равны.

Содержание