Граф Screenshot_9

Определение: Графом называется геометрическая фигура, состоящая из точек и соединяющих их линий.

Ребра называются смежными, если они имеют общую вершину.

Точки графа - это вершины графа

Виды графов

Нуль-граф - это граф G=(X, R), в котором R = f

Полный граф - граф G(X, R), в котором любая пара вершин инцидентна единственному ребру.

Примеры полных графов

Трехвершинный Screenshot_10

Четырехвершинный Screenshot_11

Пятивершинный Screenshot_12

Неполный граф - граф, в котором не построены все возможные ребра.

Ориентированный граф - граф, ребрам которых присвоено направление в ту, или иную сторону.

Неориентированный граф - граф, который не имеет ребер, которые имеют направление в ту, или иную сторону.

Дополнение графа - граф над тем же множеством вершин, что и исходный, но вершины соединены ребром тогда и только тогда, когда в исходном графе ребра нет. Screenshot_13

Плоский граф - граф, который можно нарисовать так, что бы его ребра не пересекались(нигде, кроме вершины) Screenshot_14

Формы представления графа

Матрица инцидентности - одна из форм представления графа, в которой указываются связи между инцидентными элементами графа.

Пути и циклы в графе

Маршрут в графе - это чередование вершин и ребер.

Путь в графе - это последовательность вершин, в которой каждая вершина соединена со следующим ребром.

Простой путь - последовательность дуг, в которой каждая следующая дуга имеет началом конец предыдущей, и каждая дуга встречается не более одного раза.

Цикл в графе - замкнутый маршрут.

Простой цикл в графе - цикл, в котором все вершины, кроме первой и последней попарно различны.

Связные вершины - две любые пары вершин соединены путем.

несвязые вершины - любая пара вершин не соединены путем.

Несвязный граф - в графе есть хотя бы одна несвязанная пара вершин.

связный граф - две любые вершины соединены путем