Cтраница 3
Сейчас мы установим взаимосвязь между суммами цикловых индексов для некоторой совокупности графов и соответствующей совокупности корневых графов. Граф G можно сделать корневым, взяв в качестве корня произвольную из его вершин. Два корневых графа ( G, и) и ( G, v) являются одинаковыми ( изоморфными) тогда и только тогда, когда вершины и и v принадлежат одной и той же орбите группы графа G. Множество автоморфизмов графа ( G, и) состоит из всех автоморфизмов графа G, оставляющих вершину и неподвижной. Однако для удобства мы не будем включать корень в множество объектов, на котором действует группа рассматриваемого корневого графа. Несколько злоупотребляя обозначениями, мы снова будем использовать запись Z ( ей. [31]
Сейчас мы установим взаимосвязь между суммами цикловых индексов для некоторой совокупности графов и соответствующей совокупности корневых графов. Граф G можно сделать корневым, взяв в качестве корня произвольную из его вершин. Два корневых графа ( G, и) и ( G, v) являются одинаковыми ( изоморфными) тогда и только тогда, когда вершины и и v принадлежат одной и той же орбите группы графа G. Множество автоморфизмов графа ( G, и) состоит из всех автоморфизмов графа G, оставляющих вершину и неподвижной. Однако для удобства мы не будем включать корень в множество объектов, на котором действует группа рассматриваемого корневого графа. [32]
Каждый обыкновенный граф обладает, по крайней мере, одним собственным изоморфизмом, а именно, тривиальным изоморфизмом, при котором каждая вершина и ребро соответствуют самим себе. Изоморфизм графа с самим собой называется автоморфизмом. Совокупность автоморфизмов графа образует группу, называемую группой графа. Порядок группы называется симметрическим числом графа. Задача о том, является ли каждая перестановочная группа в общем случае группой графа, до сих пор не решена. Она возникает при определении числа неизоморфных графов с заданной перестановочной группой. [33]