Некоторые виды графов
Определение. Граф такой, что любые две его вершины смежны, называется полным графом. Полный граф с р вершинами обозначается . На рис. 6 показаны графы .
Рис. 6
Степень каждой вершины графа Кр равна . Следовательно, число ребер графа Кр равно .
Определение. Граф называется регулярным степени k, если все его вершины имеют одну и туже степень k. На рис. 7 приведены примеры регулярных графов степени 3. Всякий полный граф Кр – это регулярный граф степени .
Рис.7
Определение. Граф с пустым множеством ребер называется вполне несвязным графом. Вполне несвязный граф с р вершинами будем обозначать через Np. Граф N 1, состоящий из единственной вершины, называется тривиальным графом.
Определение. Граф называется двудольным, если множество его вершин V можно разбить на два непересекающихся подмножества V 1 и V 2, называемых долями, (V 1 V 2 = V, V 1 V 2 = Æ) так, что ребра графа соединяют только вершины разных множеств. Двудольный граф обозначим .
Полный двудольный граф у которого обозначим Km,n. Если m = 1 (или n = 1), то граф называется звездой.
На рис. 8 показан двудольный граф и полные двудольные графы K 2,3 и K 1,5 (K 1,5 - звезда).
Дата добавления: 2015-09-27 | Просмотры: 483 | Нарушение авторских прав
|