Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ГЕОМЕТРИЧЕСКАЯ ТЕОРИЯ ГРАФОВ
Посмотреть оригинал

Некоторые классы конечных графов

Некоторые конечные графы имеют в литературе специальные названия. Охарактеризуем наиболее часто употребляемые термины.

Элементарные графы

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

Элементарные графы с петлями

Конечный граф без параллельных ребер (и без параллельных петель) называется элементарным графом с петлями. Элементарный граф является его частным случаем. Для элементарного графа с петлями можно использовать упрощенное определение (без упоминания отображения инциденции). Именно этот граф определяется как совокупность непустого множества V (множество вершин) и любого подмножества ? из V&V (множество

ребер). Ясно, что если |у| = п, то |?| < п + С„2 = П + ^ .

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

с петлями. В этом случае, если

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

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы