Граф
Определение: Графом называется геометрическая фигура, состоящая из точек и соединяющих их линий.
Ребра называются смежными, если они имеют общую вершину.
Точки графа - это вершины графа
Виды графов
Нуль-граф - это граф G=(X, R), в котором R = f
Полный граф - граф G(X, R), в котором любая пара вершин инцидентна единственному ребру.
Примеры полных графов
Трехвершинный
Четырехвершинный
Пятивершинный
Неполный граф - граф, в котором не построены все возможные ребра.
Ориентированный граф - граф, ребрам которых присвоено направление в ту, или иную сторону.
Неориентированный граф - граф, который не имеет ребер, которые имеют направление в ту, или иную сторону.
Дополнение графа - граф над тем же множеством вершин, что и исходный, но вершины соединены ребром тогда и только тогда, когда в исходном графе ребра нет.
Плоский граф - граф, который можно нарисовать так, что бы его ребра не пересекались(нигде, кроме вершины)
Формы представления графа
Матрица инцидентности - одна из форм представления графа, в которой указываются связи между инцидентными элементами графа.
Пути и циклы в графе
Маршрут в графе - это чередование вершин и ребер.
Путь в графе - это последовательность вершин, в которой каждая вершина соединена со следующим ребром.
Простой путь - последовательность дуг, в которой каждая следующая дуга имеет началом конец предыдущей, и каждая дуга встречается не более одного раза.
Цикл в графе - замкнутый маршрут.
Простой цикл в графе - цикл, в котором все вершины, кроме первой и последней попарно различны.
Связные вершины - две любые пары вершин соединены путем.
несвязые вершины - любая пара вершин не соединены путем.
Несвязный граф - в графе есть хотя бы одна несвязанная пара вершин.
связный граф - две любые вершины соединены путем