Помощь - Поиск - Пользователи - Календарь
Полная версия: дискретная математика. задача
Форум «Всё о Паскале» > Образование и наука > Математика
Николай
Помогите пожалуйста.
1.При каких n существуют графы с n вершинами, каждая их которых имеет степень 3? степень 4?.
2.Перчислить все попарно неизоморфные ориентированные графы без петель с 3-мя вершинами и 3-мя ребрами.
Гость
3.Определить число ребер в:
полном графе с n вершинами,вкотором 2 любые вершины смежны(Kn);
полном двудольном графе(Kn,q).
4.Найти радиус и диаметр каждого из графов:
полном графе с n вершинами,вкотором 2 любые вершины смежны(Kn);
полном двудольном графе(Kn,q);
и еще какое то Сn.
Гость
Ну блин что никто не знает ?
Atos
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)
Гость
Уважаемый Atos, Вы не можете нарисовать графы к 4-му заданию?
Обьясните почему 2 графа а не 4 во 2-м задании?
В третем задании это делаеться по формулам?
Atos
Цитата
Обьясните почему 2 графа а не 4 во 2-м задании?
Вот 2 графа. Откудa взяться ещё двум?Нажмите для просмотра прикрепленного файла
Цитата
В третем задании это делаеться по формулам?
Эти формулы выводятся из общих соображений. В Kn каждая из n вершин соединена с n-1 остальными. каждое ребро соединяет 2 вершины, поэтому делим на 2. Вот со второй формулой я немного ошибся, извиняюсь... В K(n,q) каждая из n вершин соединена с q противоположными, и тут делить на два не надо было... просто n*q.
Цитата
Вы не можете нарисовать графы к 4-му заданию?
Полный граф - каждая вершина соединена с каждой. полный двудольный - вершины разбиты на два множества, и каждая вершина соединена со всеми из противоположного множества. Cn - это простой n-вершинный цикл (замкнутая цепочка). Разве нет учебника с рисунками?
Лена
помогите доказать:
Докажите, что в любом графе есть либо три попарно смежные, либо три попарно несмежные вершины
За ранее спасибо!!! blink.gif
Michael_Rybak
Этого нельзя доказать. Это недоказуемо.
мисс_граффити
...зато легко доказать обратное.
если в графе всего две вершины...
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.