logo e1.ru
Мои фотоальбомы
Настройки форумов
Паспорт
Выйти
Поиск по форумам
Общение
Автоклуб
Общение Автоклуба

есть ли математики в форуме? нуно узнать кое-что..

Общение Автоклуба
ч
блина, замучился гуглить... может кто по-простому сказать, надо.

в ориентированном графе G(V,E) n вершин. Он полный! (важно, значит кол-во ребер известно - n*(n-1) )

как узнать максимально возможное число циклов в нем?

очень надо. спасибо!
0
B
Billy2
Теорию графов надо читать. Спроси у препода на консультации. Графы - это польза.
0
З
Задний ум
Не помогайте ему... пока в долю не возьмёт.
20:31

Это он отмычку хочет изобрести к графическим ребусам программы "Деньги на проводе" на ТНТ.
И не поделиться... редиска.
0
ч
ч13
флудеров прошу выйти из темы, плииииз. спасибо.
0
B
Billy2
а мы не флудеры, мы стараемся помочь.
0
М
Магистр Йода™
цикл бывает по ребрам и по вершинам
если по вершинам, то неясно зачем нужна ориентированность графа

исправился

[Сообщение изменено пользователем 10.01.2007 21:45]
0
ч
ч13
От пользователя Магистр Йода™
цикл бывает по ребрам и по вершинам
если по вершинам, то неясно зачем нужна полнота графа

цикл - это замкнутый путь. путь - по вершинам так-то.
просто есть полный граф. зная кол-во вершин, надо знать максимально возможное количество циклов.
0
B
Billy2
От пользователя Магистр Йода™
если по вершинам, то неясно зачем нужна ориентированность графа


в ориентированном графе циклов меньше чем в ориентированном, т.к. ориентация определяет напрвление движения
0
М
Магистр Йода™
От пользователя x13™
путь - по вершинам так-то.

если вам фантазия не позволяет представить путь по "дорожкам" между вершинами, я тут не виноват :-)

формулы готовой не знаю, но думаю что она если и есть так как-то индуктивно выражается через графы меньших размеров...
циклы кстати полные или любые?
0
М
Магистр Йода™
От пользователя Billy2
в ориентированном графе циклов меньше чем в ориентированном, т.к. ориентация определяет напрвление движения

в каком меньше???
если граф полный то можно идти хоть куда, стало быть направление пох, не так ли?
0
ч
ч13
От пользователя Магистр Йода™
циклы кстати полные или любые?

я не знаю что вы подразумеваете под термином полные, но мне нужны любые, и формула конечно нужна, а не догадки.... :-)
0
М
Магистр Йода™
От пользователя x13™
я не знаю что вы подразумеваете под термином полные

те которые через все вершины
0
Ш
Шико
От пользователя Магистр Йода™
если граф полный то можно идти хоть куда, стало быть направление пох, не так ли?

Я так понял, что количество циклов отличается ровно вдвое (каждый неориентированный цикл можно пройти в двух направлениях).

Теперь временно забудем про ориентированность графа. Поскольку граф полный, то любые k вершин образуют цикл. Количество таких циклов длинны k равно кол-ву сочетаний из n по k. Осталось просуммировать по всем возможным k, а именно от 3 до n (циклы длинны один и два в природе не встречаются :-) ).
0
М
Магистр Йода™
соглашусь с предыдущим оратором :-)
0
Ш
Шико
А если не секрет, откуда задачка взялась? ;-)
0
З
Задний ум
22:03 22:07
А теперь ещё раз [21:33].
0
B
Billy2
От пользователя Шико


теперь добавить ориентированность графа. про неориентированный все правильно
0
М
Магистр Йода™
От пользователя Шико
Поскольку граф полный, то любые k вершин образуют цикл

может все же не 1 цикл? ребра то разные можно брать
из 3 вершин 1 цикл, из 4 уже 2, и так далее...
0
C
Crasher
От пользователя Задний ум
22:03 22:07
А теперь ещё раз [21:33].

для ТНТ какая то сложная игра :-)
0
ч
ч13
От пользователя Шико
откуда задачка взялась?

да так, надо тут формулу красивую написать, одна из зависимостей -- циклы. (диссер)
0
Т
Теоретик
про неориентрировнные графы:

http://www.research.att.com/~njas/sequences/A002807

[Сообщение изменено пользователем 10.01.2007 23:46]
0
ч
ч13
От пользователя Теоретик
про неориентрировнные графы:

Спасибо большое!!
Про орграфы тоже, я надеюсь найти формулу, хотя и это на первом этапе сойдет. Спасибо!
0
Е
Е1.RU
Тема автоматически закрыта.
0
Общение Автоклуба
Обсуждение этой темы закрыто модератором форума.