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

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

Прочитайте:
  1. X. НЕКОТОРЫЕ ВЫВОДЫ
  2. Дополнительные характеристики графов
  3. Изоморфизм графов
  4. Изоморфизм графов.
  5. Изоморфизм графов.
  6. Изоморфность графов
  7. История возникновения теории графов
  8. Классы графов.
  9. Некоторые дополнительные наименования анемий приведены в статье «Анемии» приложения «Справочник терминов».

Определение. Граф такой, что любые две его вершины смежны, называется полным графом. Полный граф с р вершинами обозначается . На рис. 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 | Нарушение авторских прав







При использовании материала ссылка на сайт medlec.org обязательна! (0.004 сек.)