Классификация графов

Полный граф –граф, у которого все вершины попарно смежные (рис. 1.4.). Так как для полного графа p(x₁)= p(x₂)= …= p(x_n)=n-1, то число ребер в таком графе

(1.4)

Связный граф - неориентированный граф, у которого из любой вершины есть путь в любую другую вершину (путь может состоять из любого количества рёбер). На рис. 1.5 граф является связным.

Несвязанный граф – граф, состоящий из отдельных фрагментов. Если у графа на рис 1.5 удалить ребро между вершинами 4 и 5, то связным он не будет - из вершины 5 нельзя будет попасть ни в какую другую вершину.

Изолированная вершина – вершина, которой не инцидентно ни одно ребро.

Пустой граф – граф, состоящий только из изолированных вершин.

Висячая вершина– вершина степень, степень которой равна 1.

Граф G'=(X',U')называется частью графа G=(X,U), если X'ÍX, U'ÍUи обозначается G'ÍG,т.е. часть графа – это граф, полученный из исходного графа исключением некоторых вершин и некоторых ребер.

Часть графа G'=(X',U')называют подграфомграфа G=(X,U), если X'ÍX, а множество ребер U'ÍUобразовано всеми ребрами, соединяющими между собой только вершины из X',т.е.подграф -граф, полученный из исходного графа исключением некоторых вершин и всех инцидентных им ребер.

Часть графа G'=(X',U')называют суграфом графа G=(X,U), если X'=X,аU'ÍU, т.е.суграф- граф, полученный из исходного графа исключением некоторых ребер.

Объект G_i=(X_i,U_i), называется куском графа G=(X,U), если X_iÍX, U_iÍU, причемU_i=U_iiÈU_ij, где U_ii-множество ребер соединяющих вершины из X_i между собой, а U_ij - множество ребер, один конец которых принадлежит X_i, а второй X\X_i, т.е. X_i - подмножество X, а в U_i входят все ребра из U, инцидентные X_i.Другими словами, кусок графа G(Z,U) – это граф Q(X,Y), являющийся частью исходного графа такой, что X — подмножество Z, а в Y входят все ребра из U, инцидентные X.

Пример: