Упр.82 ГДЗ Бунимович Булычев 10 класс (Алгебра)

Сколько рёбер нужно удалить из графа, изображённого на рисунке 57, чтобы получилось дерево? Удалите их и перерисуйте полученное дерево в тетрадь.

Чтобы из графа получить дерево, нужно удалить столько рёбер, чтобы граф стал связным и в нём не осталось циклов. Для связного графа с $$n$$ вершинами дерево содержит $$n-1$$ ребро.

Значит, число рёбер, которые нужно удалить, равно разности между числом рёбер графа и числом рёбер дерева.

1. а) В графе $$n=6$$ вершин и $$6$$ рёбер. Тогда в дереве должно быть $$6-1=5$$ рёбер, значит, удалить нужно

   $$6-5=1.$$

2. б) В графе $$n=5$$ вершин. Число рёбер в дереве:

   $$5-1=4.$$

   В данном графе рёбер $$10$$, значит, удалить нужно

   $$10-4=6.$$

3. в) В графе $$n=7$$ вершин. Число рёбер в дереве:

   $$7-1=6.$$

   В графе рёбер $$7$$, значит, удалить нужно

   $$7-6=1.$$

Ответ

а) 1 ребро; б) 6 рёбер; в) 1 ребро.