22.07.2017, 03:48 [+3 UTC]
в нашей команде: 2 065 чел. | участники онлайн: 1 (рекорд: 21)

:: РЕГИСТРАЦИЯ

:: консультации

:: задать вопрос

:: все разделы

:: правила

:: новости

:: участники

:: доска почёта

:: форум

:: блоги

:: поиск

:: статистика

:: наш журнал

:: наши встречи

:: наша галерея

:: отзывы о нас

:: поддержка

:: руководство

Версия системы:
7.41 (25.02.2017)

Общие новости:
23.02.2017, 09:51

Форум:
21.07.2017, 11:30

Последний вопрос:
20.07.2017, 15:47

Последний ответ:
21.07.2017, 15:17

Последняя рассылка:
21.07.2017, 15:15

Писем в очереди:
0

Мы в соцсетях:

Наша кнопка:

RFpro.ru - здесь вам помогут!

Отзывы о нас:
29.12.2011, 23:20 »
Тарас
Огромное спасибо! Ваш сайт очень полезен, откровенен и очень полезный, самое главное правдивый, Вы помогаете людям, и самое главное не отступить от этих принципов !
22.01.2012, 20:04 »
Даровко Антон Владимирович
Я посмотрел Ваше решение задачи и оценил его на отлично. [вопрос № 185237, ответ № 269660]
20.01.2012, 18:47 »
Sanek
Спасибо за помощь))) [вопрос № 185217, ответ № 269653]

РАЗДЕЛ • Математика

Консультации и решение задач по алгебре, геометрии, анализу, дискретной математике.

[администратор рассылки: Лысков Игорь Витальевич (Старший модератор)]

Лучшие эксперты в этом разделе

Гордиенко Андрей Владимирович
Статус: Модератор
Рейтинг: 2976
Лысков Игорь Витальевич
Статус: Старший модератор
Рейтинг: 295
Megaloman
Статус: Академик
Рейтинг: 154

Перейти к консультации №:
 

Консультация онлайн # 137574
Раздел: • Математика
Автор вопроса: Sashka
Отправлена: 19.05.2008, 22:39
Поступило ответов: 1

Здравствуйте! Вопрос по теории графов. Решал задачу, в которой нужно найти ейлеров и гамильтонов циклы. Я знаю, что цикл. ейлеров путь, это тот который проходит по всем ребрам в точности по одному разу и возвр. в начальную вершину. Я доказал, что циклического ейлерового не существует т.к. степень почти всех вершин - непарная. и что не существует не цикл. ейл. путь (по одной теореме). Подскажите как доказать, что не существует или существует цикл. или нецикл. гамильтонов маршрут. Просто теорию вкратце. Спасибо заранее.

Состояние: Консультация закрыта

Здравствуйте, Sashka!

Между эйлеровыми и гамильтоновыми линиями имеется определенная аналогия. Эйлерова линия проходит один раз по каждому ребру, а гамильтонова – через каждую вершину. Но существует и большая разница.

Эилер доказал, что если степени всех вершин связного графа четны, то на таком графе можно найти цикл, содержащий все ребра этого графа, причем в точности по одному разу. Для гамильтонова цикла общего критерия, насколько мне известно, не существует. Поэтому для того, чтобы доказать, что на конкретном графе гамильтонов цикл существует, надо его найти…

Существуют лишь некоторые критерии для частных случаев. Например, если для любой пары вершин графа сумма локальных степеней больше или равна числу вершин графа, то в таком графе существует гамильтонов цикл… Полагаю, что специалисты по дискретной математике дадут более исчерпывающие справки.

С уважением.


Консультировал: Гордиенко Андрей Владимирович (Модератор)
Дата отправки: 21.05.2008, 00:33

Рейтинг ответа:

0

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

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

Яндекс Rambler's Top100

главная страница | поддержка | задать вопрос

Время генерирования страницы: 0.13337 сек.

© 2001-2017, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.41 от 25.02.2017
Бесплатные консультации онлайн