Пример 3. Заметим, что степень каждой вершины полного графа равна , так что
Заметим, что степень каждой вершины полного графа равна , так что
.
Следовательно, число ребер полного графа с вершинами равно .
Определение. Граф H называется подграфом графа G, если .
Двудольным графом называется обыкновенный граф, множество вершин которого может быть разбито на два непустых непересекающихся подмножества (доли), так что концы каждого ребра графа принадлежат разным долям.
Двудольный граф называется полным двудольным графом, если любые две его вершины, принадлежащие разным долям, смежные.
Полный двудольный граф с вершинами в одной доле и вершинами в другой () обозначают .
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
studopedia.su - Студопедия (2013 - 2025) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав!Последнее добавление