1 Тема от Acmefan

  • Acmefan
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-03-24
  • Сообщений: 32

Тема: Определить или граф есть деревом

Задача:
Определить или неориентированнй взвешенный граф является деревом.

Решить просто: количество ребер должно быть N-1 (где N - количество вершин) и запустить поиск в глубину - проверить связность.

Но посетила мысль! А нельзя ли проще:
проверить количество ребер, что б было N-1 и проверить что б не было вершин со степенью 0. (иключение вариант с одной вершиной).

Верен ли этот метод?

2 Ответ от cmd

  • cmd
  • Участник
  • Неактивен
  • Откуда: Волжский
  • Зарегистрирован: 2009-06-11
  • Сообщений: 35

Re: Определить или граф есть деревом

Тест:
Количество вершин = 7, количество ребер 6
Граф:
1 - 2
2 - 3

4 - 5
5 - 6
6 - 7
7 - 5

Вершин со степень 0 нет, количество ребер = количество вершин - 1.
Без проверки на связность видимо никак.

3 Ответ от Acmefan

  • Acmefan
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-03-24
  • Сообщений: 32

Re: Определить или граф есть деревом

да, точно.
могут же быть циклы в компонентах связности.

А так хотелось проверять "жлобским методом" smile

4 Ответ от rauf

  • rauf
  • Участник
  • Неактивен
  • Зарегистрирован: 2011-05-05
  • Сообщений: 2

Re: Определить или граф есть деревом

We can find it using BFS.
when we reach each node we must increment its degree by one..
if we see that there some nodes with degree >=2 then graph is not tree.