АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Некоторые виды графов

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

Рис. 6

Степень каждой вершины графа К_р равна . Следовательно, число ребер графа К_р равно .

Определение. Граф называется регулярным степени k, если все его вершины имеют одну и туже степень k. На рис. 7 приведены примеры регулярных графов степени 3. Всякий полный граф К_р – это регулярный граф степени .

Рис.7

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

Определение. Граф называется двудольным, если множество его вершин V можно разбить на два непересекающихся подмножества V ₁ и V ₂, называемых долями, (V ₁ V ₂ = V, V ₁ V ₂ = Æ) так, что ребра графа соединяют только вершины разных множеств. Двудольный граф обозначим .

Полный двудольный граф у которого обозначим K_m,n. Если m = 1 (или n = 1), то граф называется звездой.

На рис. 8 показан двудольный граф и полные двудольные графы K _2,3 и K _1,5 (K _1,5 - звезда).

Дата добавления: 2015-09-27 | Просмотры: 483 | Нарушение авторских прав