Таблицы Брадиса

Пусть один их них Саша.

Пусть один их них Саша.

Элементы математики в задачах - Г. А. Мерзон

В случае положительного ответа обычно просто предъявляется би­екция между множествами вершин. Для доказательства неизоморф­ности двух графов требуются более тонкие соображения. Например, для каждого графа можно посчитать некоторые величины, которые одинаковы для изоморфных графов (число вершин, число ребер, число вершин данной степени и т. д.). Такие величины называются инвариантами и часто используются, например, для доказательства неизоморфности различных математических объектов.

Задача 2. Нарисуйте все неизоморфные друг другу графы с не более

чем четырьмя вершинами.

Указание. Разумно перечислять эти графы, упорядочивая их по числу вершин и числу ребер.

Решение. Существует только один граф, в котором 0 вершин и только один граф, в котором одна вершина:

Графов с двумя вершинами существует два: тот, в котором эти вер­шины соединены ребром, и тот, в котором не соединены:

Существует четыре графа с тремя вершинами: без ребер, с одним, двумя и тремя ребрами:

 

 

Теория графов 1

 

Графов с четырьмя вершинами и двумя (соответственно, четырьмя) ребрами существует по два:

 

Графов с четырьмя вершинами и тремя ребрами три:

 

-£>

 

б) Допустим, нашлась компания, в которой нет ни трех попарно знакомых человек, ни трех попарно незнакомых. Пусть один их них Саша. Так как кроме него в компании еще 5 человек, он либо знаком хотя бы с тремя людьми этой компании, либо незнаком хотя бы с тре­мя. Без ограничения общности можно считать, что Саша знаком хотя бы с тремя людьми из этой компании. Если какие-то двое из Сашиных знакомых знакомы между собой, они вместе с Сашей образуют тройку