Таким образом, каждая вершина в подграфе графа G (обозначен в определении как G со штрихом) является также вершиной в графе G, и каждое ребро в подграфе графа G является ребром и в графе G. Итак, рассмотрим несколько типов подграфов: Пример 1. Рассмотрим граф G (см. рис. ниже). Число остовных подграфов графа G определяется по формуле 2 в третьей степени = 8. Перечислим все 8 остовных подграфов (см. рис. ниже) Пример 2. Рассмотрим граф G (см. рис. выше). Число вершинно-порожденных подграфов графа G определяется по формуле 2 в четвёртой степени – 1 = 15...

Начало: Математика для чайников. Глава 1. Что такое математическая абстракция. Предыдущая глава: Математика для чайников. Глава 14. Производная Важность теории графов трудно переоценить. Казалось бы, что такое граф? Просто набор стрелочек. Просто схема. Но вокруг этой незамысловатой схемы из стрелочек построена целая теория. И эта теория нашла очень широкое применение. Но почему? Давайте разберемся. Где можно применить такой объект, как граф? Первым делом напрашивается задача построения маршрута, как это делают навигаторы...