Род графа

Материал из WikiGrapp
Перейти к:навигация, поиск

Род графа (Genus of a graph) — наименьшее число \gamma(G) ручек, которые необходимо добавить к сфере, чтобы граф G можно было уложить на полученной таким образом поверхности. Очевидно, что \gamma(G) = 0 тогда и только тогда, когда G планарный, и \gamma(G) = 1 тогда и только тогда, когда G тороидальный.

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.