Обсуждение участницы:Анна

Перечисления графов

Помеченные графы

Определение:

Помеченный граф с [math]n[/math] вершинами — граф, у которого каждая вершина помечена целым числом от [math]1[/math] до [math]n[/math].

Более формально определить это понятие можно так: назовем распределением [math]f[/math] меток в графе [math]G[/math] с [math]n[/math] вершинами биекцию между множеством вершин графа и множеством [math]\{1 \cdots n\}[/math]. Тогда помеченным графом называется пара [math](G, f)[/math].

Определение:

Два помеченных графа [math](G_{1}, f_{1})[/math] и [math](G_{2}, f_{2})[/math] изоморфны, если существует изоморфизм между [math]G_{1}[/math] и [math]G_{2}[/math], сохраняющий распределение меток.