Понятие графа. Виды графов

граф – это множество V точек, определенным образом соединенных между собой линиями, необязательно прямыми. Точки множества V называются вершинами графа, а соединяющие их линии – ребрами. Вершины графа обычно нумеруют десятичными числами, но можно использовать и любые другие знаки. Если вершины пронумерованы, то ребра обозначают неупорядоченными парами номеров вершин. Каждую пару образуют номера тех вершин, которые соединены ребром.

Граф называется простым (или линейным), если любые две его вершины соединены не более чем одним ребром и каждое ребро соединяет различные вершины.

Всякий простой граф может быть представлен не только в виде рисунка, но и аналитически. Пусть E – множество ребер графа, тогда можно записать (рисунок 5.1):

V = {1, 2, 3, 4, 5, 6, 7},

E = {{1,2}, {1,3}, {1,4}, {1,7}, {2,5}, {2,6}, {2,7},{3, 4}, {3, 6}, {4, 5}, {4, 6}, {5,7}},

где E – множество двухэлементных подмножеств множества V, каждое из которых определяет ребро, соединяющее вершины и .

Существуют графы, в которых те или иные пары вершин соединены не одним ребром, а несколькими. Такие ребра называют кратными (параллельными).

Граф может содержать ребра, соединяющие какую-либо вершину саму с собой. Такие ребра называются петлями.

Вершина называется изолированной, если у нее нет петель и из нее не выходит ни одного ребра.

Граф, содержащий петли или кратные ребра, называется псевдографом.

Псевдограф без петель называется мультиграфом.

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

Непустой подграф называется собственным, если он не совпадает с исходным графом G. Граф G и пустой граф называются несобственными подграфами (по аналогии с несобственными подмножествами).

Граф, в котором нет ни одного ребра, называется нульграфом.

Если в графе G все вершины оставить на своих местах и удалить одно или несколько ребер, то получится частичный граф.