14:11 

Задания по теории графов

Вот не приходят идеи мне к этим 2 задачкам по теории графов:
1) Доказать, что в мультиграфе всякий замкнутый маршрут нечетной длины l>=3 содержит простой цикл. Доказать, что это несправедливо для маршрутов четной длины.
мои мысли
2) Пусть p(G) - наименьшая из степеней вершин графа G, не имеющего петель и кратных ребер и содержащего n вершин (n >= 2)
Доказать, что если p(G) >= (n-1)/2, то граф связен.
очевидное рассуждение

@темы: Дискретная математика, Теория графов

Комментарии
2016-02-28 в 18:18 

Дилетант
На плечах гигантов, на спинах электронов
2) Лучше всего доказывать от противного. Пусть для каждой вершины выполняется неравенство p(G) >= (n-1)/2 и при этом граф имеет две компоненты связности.
В одной из компонент количество вершин будет <= n/2. А степени всех вершин >= (n-1)/2. Нужно показать, что такой граф будет иметь кратные ребра либо петли.
Понятно, что чем меньше компонента, тем больше будет кратных ребер. Поэтому рассмотрим случай, когда граф поделен на две равные части (при четном n).
Если n - четно, пусть n/2=k, тогда степени вершин >=k. Поскольку у каждой вершины ровно k-1 сосед, то следовательно есть кратные ребра или петли.
Для n нечетного похожие рассуждения.

1) с чего это маршрут обязан иметь простой цикл.
С того, что он замкнутый. Но условие не очень понимаю.

     

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная