Страница 1 из 1
Определиь является граф - эйлеровым графом ?
Добавлено: 01 ноя 2012, 15:03
Kravcos
Составить алгоритм, с помощью которого для произвольного конечного неориентированного графа с n вершинами (1 <= n <= 20), который задается матрицей смежности. Определить не является ли он эйлеровым графом.
Пожалуйста помогите кто может ...
Очень буду благодарный )))
Re: Определиь является граф - эйлеровым графом ?
Добавлено: 11 ноя 2012, 07:16
dr.Jekill
Достаточно проверить, чтобы граф не содержал одиночные вершины и
вершины нечетной степени.
Если найдена хотя бы одна такая вершина, то граф не эйлеров
Re: Определиь является граф - эйлеровым графом ?
Добавлено: 12 ноя 2012, 21:57
Kravcos
dr.Jekill писал(а):Достаточно проверить, чтобы граф не содержал одиночные вершины и
вершины нечетной степени.
Если найдена хотя бы одна такая вершина, то граф не эйлеров
не бог бы ты показать или написать как это сделать... (навести пример), а то я не очень понял...(
Re: Определиь является граф - эйлеровым графом ?
Добавлено: 24 ноя 2012, 03:47
dr.Jekill
Одиночные вершины - это вершины не соединенные с другими.
Вершины нечетной степени - это вершины соединенные с нечетным количеством вершин.
Просто считайте количество вершин, с которыми соединена каждая вершина, пока:
1. не найдете вершину не соединенную ни с одной другой;
2. или соединенную с нечетным количеством вершин;
3. или не завершите обход.
При этом т.к. граф неориентированный, то матрица смежности симметрична и соотв. достаточно обработать только элементы выше главной диагонали.
Что из этого Вам непонятно? - задавайте вопросы - постараюсь ответить