Тег «графы»

Красота – редкая вещь

Здесь мы будем рассматривать графы. Напомним, что степенью вершины графа называется количество ребер, инцидентных этой вершине. Граф называется регулярным, если все его вершины имеют одинаковую степень. Обхватом графа называется наименьшая длина цикла в этом графе.

Рассмотрим графы обхвата 5. Какое наименьшее число вершин может иметь данный граф, если степень каждой его вершины равна r?

Возьмем вершину u. У нее r смежных вершин. Каждая из этих вершин имеет еще r-1 смежную вершину. Итак, имеем 1+r+r(r-1)=r^2+1 вершин. Они все должны быть различными, иначе появится цикл длины \le 4.

Возникает естественный вопрос: нужны ли нам еще вершины? Давайте посмотрим. Для r=2 имеем r^2+1=5, и получаем пятиугольник, один цикл длины 5. Для r=3 имеем r^2+1=10 вершин. Это опять-таки возможно. Такой граф единственен, и это граф Петерсена, который воистину замечателен большим количеством симметрий, или автоморфизмов (их 120):

Читать полностью ‘Красота – редкая вещь’ »