Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Подграфы



Граф называется подграфом графа , если , . Всякий подграф может быть получен из графа удалением некоторых вершин и ребер (при удалении вершины удаляются и все инцидентные ей ребра).

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

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





Дата публикования: 2014-11-26; Прочитано: 263 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2025 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.444 с)...