Версия для печати темы

Автор: Николай 20.01.2006 21:23

Помогите пожалуйста.
1.При каких n существуют графы с n вершинами, каждая их которых имеет степень 3? степень 4?.
2.Перчислить все попарно неизоморфные ориентированные графы без петель с 3-мя вершинами и 3-мя ребрами.

Автор: Гость 21.01.2006 1:05

3.Определить число ребер в:
полном графе с n вершинами,вкотором 2 любые вершины смежны(Kn);
полном двудольном графе(Kn,q).
4.Найти радиус и диаметр каждого из графов:
полном графе с n вершинами,вкотором 2 любые вершины смежны(Kn);
полном двудольном графе(Kn,q);
и еще какое то Сn.

Автор: Гость 21.01.2006 3:14

Ну блин что никто не знает ?

Автор: Atos 21.01.2006 19:22

1. Это полные графы K4 и K5 соответственно.

2. Таких графов всего два. Подумай и нарисуй сам

3.
a) (n-1)*n/2
б) n*q/2

4. Для всех этих графов радиус равен диаметру
a) r=d=1
б) r=d=2
в) r=d=целая часть(n/2)

Автор: Гость 21.01.2006 21:51

Уважаемый Atos, Вы не можете нарисовать графы к 4-му заданию?
Обьясните почему 2 графа а не 4 во 2-м задании?
В третем задании это делаеться по формулам?

Автор: Atos 23.01.2006 11:14

Вот 2 графа. Откудa взяться ещё двум?
Эти формулы выводятся из общих соображений. В Kn каждая из n вершин соединена с n-1 остальными. каждое ребро соединяет 2 вершины, поэтому делим на 2. Вот со второй формулой я немного ошибся, извиняюсь... В K(n,q) каждая из n вершин соединена с q противоположными, и тут делить на два не надо было... просто n*q.
Полный граф - каждая вершина соединена с каждой. полный двудольный - вершины разбиты на два множества, и каждая вершина соединена со всеми из противоположного множества. Cn - это простой n-вершинный цикл (замкнутая цепочка). Разве нет учебника с рисунками?

Автор: Лена 23.01.2007 21:07

помогите доказать:
Докажите, что в любом графе есть либо три попарно смежные, либо три попарно несмежные вершины
За ранее спасибо!!!

Автор: Michael_Rybak 24.01.2007 2:09

Этого нельзя доказать. Это недоказуемо.

Автор: мисс_граффити 24.01.2007 2:14

...зато легко доказать обратное.
если в графе всего две вершины...