
Форумы > Автоклуб > Общение Автоклуба

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

Список Тем | Поиск | Правила | Статистика |

есть ли математики в форуме? нуно узнать кое-что..	^#2094843	^наверх
Автор: ч13 Дата: 10 января 2007 20:31 блина, замучился гуглить... может кто по-простому сказать, надо. в ориентированном графе G(V,E) n вершин. Он полный! (важно, значит кол-во ребер известно - n*(n-1) ) как узнать максимально возможное число циклов в нем? очень надо. спасибо!
0/0 \| \| Поделиться:

Re: есть ли математики в форуме? нуно узнать кое-ч...	^#2094962	^наверх
Автор: Billy2 Дата: 10 января 2007 21:25 Теорию графов надо читать. Спроси у препода на консультации. Графы - это польза.
0/0 \| \| Поделиться:

Маня должна быть довольна	^#2094982	^наверх
Автор: Задний ум Дата: 10 января 2007 21:33 Не помогайте ему... пока в долю не возьмёт. 20:31 Это он отмычку хочет изобрести к графическим ребусам программы "Деньги на проводе" на ТНТ. И не поделиться... редиска.
0/0 \| \| Поделиться:

Re: Маня должна быть довольна	^#2094999	^наверх
Автор: ч13 Дата: 10 января 2007 21:37 флудеров прошу выйти из темы, плииииз. спасибо.
0/0 \| \| Поделиться:

Re: Маня должна быть довольна	^#2095024	^наверх
Автор: Billy2 Дата: 10 января 2007 21:41 а мы не флудеры, мы стараемся помочь.
0/0 \| \| Поделиться:

Re: Маня должна быть довольна	^#2095029	^наверх
Автор: Магистр Йода™ Дата: 10 января 2007 21:44 цикл бывает по ребрам и по вершинам если по вершинам, то неясно зачем нужна ориентированность графа исправился [Сообщение изменено пользователем 10.01.2007 21:45]
0/0 \| \| Поделиться:

Re: Маня должна быть довольна

^#2095039

^наверх

Автор: ч13 Свой человек в форумах: 90

Дата: 10 января 2007 21:46

Цитата:
От пользователя: Магистр Йода™

цикл бывает по ребрам и по вершинам
если по вершинам, то неясно зачем нужна полнота графа

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

| Поделиться:

Re: Маня должна быть довольна

^#2095047

^наверх

Автор: Billy2 Свой человек в форумах: 41

Дата: 10 января 2007 21:50

Цитата:
От пользователя: Магистр Йода™

если по вершинам, то неясно зачем нужна ориентированность графа

в ориентированном графе циклов меньше чем в ориентированном, т.к. ориентация определяет напрвление движения

| Поделиться:

Re: Маня должна быть довольна

^#2095070

^наверх

Автор: Магистр Йода™ Свой человек в форумах: 44

Дата: 10 января 2007 21:55

Цитата:
От пользователя: x13™

путь - по вершинам так-то.

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

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

| Поделиться:

Re: Маня должна быть довольна

^#2095072

^наверх

Автор: Магистр Йода™ Свой человек в форумах: 44

Дата: 10 января 2007 21:56

Цитата:
От пользователя: Billy2

в ориентированном графе циклов меньше чем в ориентированном, т.к. ориентация определяет напрвление движения

в каком меньше???
если граф полный то можно идти хоть куда, стало быть направление пох, не так ли?

| Поделиться:

Re: Маня должна быть довольна

^#2095085

^наверх

Автор: ч13 Свой человек в форумах: 90

Дата: 10 января 2007 21:59

Цитата:
От пользователя: Магистр Йода™

циклы кстати полные или любые?

я не знаю что вы подразумеваете под термином полные, но мне нужны любые, и формула конечно нужна, а не догадки.... :-)

| Поделиться:

Re: Маня должна быть довольна

^#2095092

^наверх

Автор: Магистр Йода™ Свой человек в форумах: 44

Дата: 10 января 2007 22:00

Цитата:
От пользователя: x13™

я не знаю что вы подразумеваете под термином полные

те которые через все вершины

| Поделиться:

Re: Маня должна быть довольна

^#2095106

^наверх

Автор: Шико
Дата: 10 января 2007 22:03

Цитата:
От пользователя: Магистр Йода™

если граф полный то можно идти хоть куда, стало быть направление пох, не так ли?

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

Теперь временно забудем про ориентированность графа. Поскольку граф полный, то любые k вершин образуют цикл. Количество таких циклов длинны k равно кол-ву сочетаний из n по k. Осталось просуммировать по всем возможным k, а именно от 3 до n (циклы длинны один и два в природе не встречаются :-) ).

| Поделиться:

Re: Маня должна быть довольна	^#2095121	^наверх
Автор: Магистр Йода™ Дата: 10 января 2007 22:07 соглашусь с предыдущим оратором :-)
0/0 \| \| Поделиться:

Re: Маня должна быть довольна	^#2095127	^наверх
Автор: Шико Дата: 10 января 2007 22:08 А если не секрет, откуда задачка взялась? ;-)
0/0 \| \| Поделиться:

Re: Маня должна быть довольна	^#2095135	^наверх
Автор: Задний ум Дата: 10 января 2007 22:10 22:03 22:07 А теперь ещё раз [21:33].
0/0 \| \| Поделиться:

Re: Маня должна быть довольна

^#2095144

^наверх

Автор: Billy2 Свой человек в форумах: 41

Дата: 10 января 2007 22:12

Цитата:
От пользователя: Шико

теперь добавить ориентированность графа. про неориентированный все правильно

| Поделиться:

Re: Маня должна быть довольна

^#2095170

^наверх

Автор: Магистр Йода™ Свой человек в форумах: 44

Дата: 10 января 2007 22:21

Цитата:
От пользователя: Шико

Поскольку граф полный, то любые k вершин образуют цикл

может все же не 1 цикл? ребра то разные можно брать
из 3 вершин 1 цикл, из 4 уже 2, и так далее...

| Поделиться:

Re: Маня должна быть довольна

^#2095172

^наверх

Автор: Crasher В Клубе Е1 18 лет

Дата: 10 января 2007 22:23

Цитата:
От пользователя: Задний ум

22:03 22:07
А теперь ещё раз [21:33].

для ТНТ какая то сложная игра :-)

| Поделиться:

Re: Маня должна быть довольна

^#2095176

^наверх

Автор: ч13 Свой человек в форумах: 90

Дата: 10 января 2007 22:24

Цитата:
От пользователя: Шико

откуда задачка взялась?

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

| Поделиться:

Re: Маня должна быть довольна	^#2095435	^наверх
Автор: Теоретик Дата: 10 января 2007 23:45 про неориентрировнные графы: http://www.research.att.com/~njas/sequences/A002807 [Сообщение изменено пользователем 10.01.2007 23:46]
0/0 \| \| Поделиться:

Re: Маня должна быть довольна

^#2095474

^наверх

Автор: ч13 Свой человек в форумах: 90

Дата: 11 января 2007 00:00

Цитата:
От пользователя: Теоретик

про неориентрировнные графы:

Спасибо большое!!
Про орграфы тоже, я надеюсь найти формулу, хотя и это на первом этапе сойдет. Спасибо!

| Поделиться:

Re: есть ли математики в форуме? нуно узнать кое-ч...	^#15461951	^наверх
Автор: Е1.RU (О пользователе) Дата: 4 августа 2015 11:56 Тема автоматически закрыта.
0/0 \| \| Поделиться:

Список Тем | Поиск | Правила | Статистика |

Обсуждение этой темы закрыто модератором форума