Я хочу проверить, является ли мой unidirected graph деревом. Дерево - это ациклический и связанный граф. У меня есть функция, которая проверяет, подключен ли граф. Поэтому достаточно быть деревом, если граф связан и | E | = | V | -1?Проверьте, не является ли однонаправленный граф деревом
Вы правы, E = V - 1 достаточно, чтобы проверить, что ваш график является деревом.
Логика в том, что каждое дерево начинается с только основной ноты (V=1, E=0, так E=V-1), а оттуда, в любое время мы добавим один узел (V=V+1), мы должны добавить ровно одно ребро (E=E+1). Это приводит к тому, что уравнение E=V-1 остается верным для всех деревьев.
Цикл возникает, когда мы соединяем два существующих узла с новым ребром (E=E+1, но V остается неизменным), приведя уравнение E=V-1 false.
Если вас интересует, вы можете прочитать о более общей формуле v - e + f = 2, где f - количество областей внутри графа, включая внешнюю область. (Дерево имеет только внешнюю область, поэтому f=1). Это правило называется формулой Эйлера, которую вы можете прочитать о on Wikipedia.
Подключено:
Это означает, что для каждой пары выбранных вершин всегда будет путь между ними.
| E | = | V | -1:
, если ваш график имеет | V | вершины и вам даны | E | = | V | -1 ребра для их соединения, тогда, если вы сформируете цикл, вы не сможете сформировать связанный граф (некоторые вершины останутся без краев).
Мы можем заключить, что этих условий достаточно.
Да, этого достаточно. –