МАЛЫЙ МЕХМАТ МГУ

Занятие 14. Графы-II

Определение. Два графа называют изоморфными, если у них одинаковое количество вершин n, и вершины каждого из этих графов можно занумеровать числами от 1 до n так, что вершины с номерами k и m первого графа соединены ребром тогда и только тогда, когда вершины с такими же номерами во втором графе соединены ребром. Таким образом, изоморфные графы — это в некотором смысле одинаковые графы. «Схема соединений» в изоморфных графах одна и та же.

1.	Нарисуйте какие-нибудь два неизоморфных графа, в каждом из которых четыре вершины.
2.	а) У двух графов число вершин и число рёбер одинаково. Следует ли отсюда, что эти графы изоморфны? б) У двух графов число вершин одинаково (и равно n), число рёбер одинаково, и при этом вершины каждого графа можно так занумеровать числами от 1 до n, что из любой вершины первого графа исходит столько же рёбер, сколько из вершины с тем же номером второго графа. Следует ли отсюда, что эти графы изоморфны?
3.	Вершинами графа G являются четыре вершины квадрата, а рёбрами — все стороны и диагонали этого квадрата. Нарисуйте граф, изоморфный графу G, чтобы рёбра не пересекались.

Определение. Циклом называют замкнутый путь по рёбрам графа, не проходящий дважды ни по какому ребру. Связный граф, не имеющий циклов, называют деревом. Вершину дерева, из которой исходит только одно ребро, называют висячей вершиной. Нетривиальным назовём дерево, у которого более одной вершины.

4.	Нарисуйте все неизоморфные деревья, у которых а) 3; б) 4; в) 5 вершин.

Теорема 1. У всякого нетривиального дерева есть хотя бы одна висячая вершина.

Доказательство. Выберем любую вершину дерева и пойдём из неё «куда идётся», никогда не поворачивая назад (то есть если мы только что прошли по какому-то ребру, то следующим шагом мы должны пойти по другому ребру, а не назад по тому же самому). Если бы мы когда-нибудь оказались в вершине, в которой уже были раньше, то получили бы цикл, а циклов в дереве нет. Значит, никакую вершину мы не можем пройти дважды. Число вершин конечно, значит, наш путь не может продолжаться до бесконечности, то есть мы неизбежно достигнем «тупика» — он и есть висячая вершина.

5.	Докажите, что у всякого нетривиального дерева есть хотя бы две висячие вершины.
6.	Существует ли дерево, у которого шесть вершин и шесть рёбер?
7.	Докажите теорему 2: у каждого дерева число рёбер ровно на 1 меньше числа вершин. Указание. Проверьте справедливость теоремы 2 для тривиального дерева, после чего запустите индукцию по числу вершин. Для доказательства индуктивного перехода воспользуйтесь теоремой 1.
8.	Дан произвольный связный граф. Докажите, что из него можно удалить несколько рёбер (не удаляя вершин), так, чтобы полученный граф был деревом.
9.	Волейбольная сетка имеет вид прямоугольника размером 50×600 клеток. Какое наибольшее число верёвочек можно перерезать так, чтобы сетка не распалась на куски?