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

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

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

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

Если вершине не инцидентно ни одно ребро, то вершина называется изолированной. Граф, состоящий только из изолированных вершин, называется пустым; если ребру инцидентна только одна вершина (ребро как бы уходит вне поля нашего зрения), то ребро называется висячим.

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

4. Часть графа называют подграфом графа G, если , а множество ребер образовано всеми ребрами, соединяющими между собой только вершины из . Граф, полученный из исходного графа исключением некоторых вершин и всех инцидентных им ребер.

5. Часть графа называют суграфом графа , если , а . Это граф, полученный из исходного графа исключением некоторых ребер.

6. Объект называется куском графа , если , , причем , где -множество ребер соединяющих вершины из между собой, а - множество ребер, один конец которых принадлежит , а второй . (В частности кусок всегда включает в себя подграф ). Граф Q(X,Y), являющийся частью исходного графа G(Z,U) такой, что X — подмножество Z, а в Y входят все ребра из U, инцидентные X

Пример:

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

Если ребра ориентированы, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом.

Если ребра не имеют ориентации, граф называется неориентированным.

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

Рис. 2.15

Петля это дуга, начальная и конечная вершина которой совпадают.

Простой граф граф без кратных ребер и петель.

Степень вершины это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер.

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

Пути, маршруты, цепи и циклы.

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

Вершины v0, vn называются связанными данным путем (или просто связанными). Вершину v0 называют началом, vn - концом пути. Если v0 = vn, то путь называют замкнутым. Число n называется длиной пути.

Маршрут в графе путь, ориентацией дуг которого можно пренебречь.

Цепь маршрут, в котором все ребра попарно различны.

Цикл замкнутый маршрут, являющийся цепью.

Маршрут, в котором все вершины попарно различны, называют простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называются простым циклом.