Подграфы

Инварианты

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

Рассмотрим следующее утверждение:

Если при преобразовании количество вершин, ребер и степень вершины являются инвариантами, то преобразование ─ изоморфизм.

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

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

Пусть задан граф G (V, E). Граф G (V , E ) называется подграфом графа G, если

V V и/или Е Е.

Если V = V, то подграф G называется остовным.

Рис 32. Остовной подграф графа 1

Дата добавления: 2014-01-06