Вопр.№12Графы опр и пр. степ. Вер. Виды графов

Графом или неориентированным графом называется упорядоченная пара G=(V,X), состоящая из конечногонепустого множества V, элементы которого называются вершинами графа и некоторого множества X неупорядоченных пар различныхэлементов из V. Элементы множества X называются ребрами графа G.

Если вопределении графа вместо множества X пар различных элементов рассматривать конечную совокупность пар различных элементов (т.е. может быть несколько одинаковых пар {vi, vj}), то объект G = (V, X) называется графом с кратными ребрами или мультиграфом.

Ребра вида {v, v} называются петлями. Если X содержит петли икратные ребра, то G = (V,X) называется графом с кратнымиребрами ипетлями или псевдографом.

Если в определении графа (мультиграфа) вместо множества (совокупности) неупорядоченных пар элементов из V рассмотреть множество (совокупность) упорядоченных пар из V, то G = (V, X) называется ориентированным графом (ориентированным мультиграфом) или орграфом В этом случае элементы множества X называются дугами. Дуга изображается стрелкой с началом в вершине v_i и концом в вершине v_j.

Степенью (валентностью) вершины v графа (мультиграфа) называется число ребер графа инцидентных вершине v (петля учитывается дважды), обозначается d(v)или deg(v).

Вершина степени 0 называется изолированной.

Вершина степени 1 называется висячей вершиной. Ребро, инцидентное висячей вершине, называется концевым ребром.

Теорема.В конечном графе число вершин нечетной степени четно.

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

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

Граф G=(V.X) называется двудольным, если существует разбиение V=V1UV2 (V1^V2=непустое множество), такое, что никакие две вершины из Vi (i=1, 2) не являются смежными. Обозначение: G =(V1UV2, X).

Двудольный граф G=(V1UV2, X)называется полным двудольным графом, если для любых v1 из V1, для любых v2 из V2 v1 инцидентна v₂. Полный двудольный граф