Таким образом, каждая вершина в подграфе графа G (обозначен в определении как G со штрихом) является также вершиной в графе G, и каждое ребро в подграфе графа G является ребром и в графе G.
Итак, рассмотрим несколько типов подграфов:
- остовные подграфы,
- вершинно-порождённые подграфы,
- рёберно-порождённые подграфы.
Пример 1. Рассмотрим граф G (см. рис. ниже).
Число остовных подграфов графа G определяется по формуле 2 в третьей степени = 8. Перечислим все 8 остовных подграфов (см. рис. ниже)
Пример 2. Рассмотрим граф G (см. рис. выше).
Число вершинно-порожденных подграфов графа G определяется по формуле 2 в четвёртой степени – 1 = 15. Итого получается 15 вершинно-порожденных подграфов, при этом среди них:
- 1 граф с 4 вершинами (первоначальный),
- 4 графа с единственной изолированной вершиной,
- 6 графов с 2 вершинами,
- 4 графа с 3 вершинами.
Приведём все 15 вершинно-порожденные подграфы (см. рис ниже) неориентированного графа G.
Пример 3. Рассмотрим граф G (см. рис. выше).
Число рёберно-порожденных подграфов графа G определяется по формуле 2 в третьей степени – 1 = 7. Приведём все рёберно-порожденные подграфы (см. рис ниже) неориентированного графа G.
В качестве Упражнения рассмотрите неориентированный граф (примеры графов см. ниже), соответствующий первой букве Вашего имени (или фамилии) в латинском написании и для него изобразите несколько остовных, вершинно-порожденных и рёберно-порожденных подграфов.
Также см. варианты размеченных неориентированных графов с небольшим числом вершин или неориентированных рёбер по ссылке (там имеются графы, представляющие собой буквы и цифры азбуки семафорного телеграфа, разработанной Клодом Шаппом):
