 |
|
Дополнительные характеристики графов
Граф называется:
· связным, если для любых вершин 
, 
есть путь из в .
· сильно связным или ориентированно связным, если он ориентированный, и из любой вершины в любую другую имеется ориентированный путь.
· деревом, если он связный и не содержит простых циклов.
· полным, если любые его две (различные, если не допускаются петли) вершины соединены ребром.
· двудольным, если его вершины можно разбить на два непересекающихся подмножества 
и 
так, что всякое ребро соединяет вершину из с вершиной из .
· k-дольным, если его вершины можно разбить на 
непересекающихся подмножества , , …, 
так, что не будет рёбер, соединяющих вершины одного и того же подмножества.
· полным двудольным, если каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества.
· планарным, если граф можно изобразить диаграммой на плоскости без пересечений рёбер.
· взвешенным, если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра.
· хордальным, если граф не содержит индуцированных циклов с длиной больше трех.
Также бывает:
· k-раскрашиваемым
· k-хроматическим
Обобщение понятия графа
Простой граф является одномерным симплициальным комплексом.
Более абстрактно, граф можно задать как тройку 
, где 
и 
— некоторые множества (вершин и рёбер, соотв.), а 
— функция инцидентности (или инцидентор), сопоставляющая каждому ребру 
(упорядоченную или неупорядоченную) пару вершин и из (его концов). Частными случаями этого понятия являются:
· ориентированные графы (орграфы) — когда 
всегда является упорядоченной парой вершин;
· неориентированные графы — когда всегда является неупорядоченной парой вершин;
· смешанные графы — в котором встречаются как ориентированные, так и неориентированные рёбра и петли;
· Эйлеровы графы — граф в котором существует циклический эйлеров путь (Эйлеров цикл).
· мультиграфы — графы с кратными рёбрами, имеющими своими концами одну и ту же пару вершин;
· псевдографы — это мультиграфы, допускающие наличие петель;
· простые графы — не имеющие петель и кратных рёбер.
Под данное выше определение не подходят некоторые другие обобщения:
· гиперграф — если ребро может соединять более двух вершин.
· ультраграф — если между элементами 
и 
существуют бинарные отношения инцидентности.
Способы представления графа в информатике
Матрица смежности
Основная статья: Матрица смежности
Таблица, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот).
Недостатком являются требования к памяти, прямо пропорциональные квадрату количества вершин.
· Двумерный массив;
· Матрица с пропусками;
· Неявное задание (при помощи функции).