577
правок
Изменения
Нет описания правки
Два помеченных графа <tex>(G_{1}, f_{1})</tex> и <tex>(G_{2}, f_{2})</tex> '''изоморфны''', если существует изоморфизм между <tex>G_{1}</tex> и <tex>G_{2}</tex>, сохраняющий распределение меток.
}}
Все помеченные графы с тремя вершинами показаны на рисунке 1. <tex>4</tex> различных графа с <tex>3</tex> вершинами приводят к <tex>8</tex> различным помеченным графам.
{| cellpadding="2"
| || [[Файл:Перечисл1.jpg|thumb|left|420px|Рис. 1. Помеченные графы с тремя вершинами.]]
|}
Для нахождения числа помеченных графов с <tex>p</tex> вершинами нужно заметить, что каждое из <tex dpi = "165"> p\choose 2</tex> возможных ребер либо принадлежит графу, либо нет.
{{Теорема
|about=1
|statement=
Число помеченных графов с <tex>p</tex> вершинами равно <tex dpi = "165"> 2^{p\choose 2}</tex>}}
Следовательно, число помеченных графов с <tex>q</tex> ребрами равно <tex dpi = "165"> {p\choose 2}\choose q</tex>
