Гамильтонов граф icon

Гамильтонов граф



НазваниеГамильтонов граф
Дата конвертации16.07.2012
Размер28,05 Kb.
ТипДокументы
скачать >>>

ГАМИЛЬТОНОВ ГРАФ.

  1. На поверхности куба проведена замкнутая восьмизвенная ломаная, вершины которой совпадают со всеми вершинами куба. Какое наименьшее число звеньев этой ломаной может совпадать с ребрами куба?

  2. Из восьми маленьких кубиков сложен куб. Можно ли, выйдя из центра большого куба и двигаясь по рёбрам маленьких кубиков, обойти все вершины маленьких кубиков, побывав в каждой ровно один раз?

  3. Дана доска 55. Может ли конь обойти все клетки, побывав на каждой по одному разу и вернуться в исходное положение?

  4. Можно ли обойти хромым королем (король не может ходить по диагоналям) все клетки шахматной доски, начав в левом нижнем углу и закончив в правом верхнем углу?

  5. Может ли конь сделать 8 ходов и вернуться в исходную клетку, побывав при этом на всех горизонталях и вертикалях шахматной доски?

  6. а). На две клетки шахматной доски выставляются черная и белая фишки. Разрешается по очереди передвигать их, каждым ходом сдвигая очередную фишку на любое свободное соседнее поле по вертикали или горизонтали. Могут ли на доске в результате таких ходов встретиться все возможные позиции расположения этих двух фишек, причем ровно по одному разу? б). А если разрешается сдвигать фишки в любом порядке (не обязательно по очереди)?

Какой из следующих трёх фактов самый «сильный»?

  1. В некотором государстве каждые 2 города соединены дорогой. На каждой дороге разрешено движение только в одну сторону. Докажите, что найдётся город, выехав из которого можно объехать всё государство, побывав в каждом городе ровно 1 раз.

  2. В некоторой стране каждый город соединён с каждым дорогой с односторонним движением. Докажите, что найдётся город, из которого можно добраться в любой другой.

  3. В некотором государстве 100 городов и каждый соединён с каждым дорогой с односторонним движением. Докажите, что можно поменять направление движения на одной дороге так, чтобы от любого города можно было доехать до любого другого.

Докажите самый «сильный» факт и оба следствия из него.

  1. В однокруговом шахматном турнире каждый участник сыграл с каждым по одной партии. Докажите, что участников можно так занумеровать, что ни один не проиграл непосредственно следующему за ним по номеру.

  2. В стране N городов. Между любыми двумя из них проложена либо автомобильная, либо железная дорога. Турист хочет объехать страну, побывав в каждом городе ровно один раз, и вернуться в город, с которого он начинал путешествие. Докажите, что турист может выбрать город, с которого он начнёт путешествие, и маршрут так, что ему придётся поменять вид транспорта не более одного раза. (Всероссийская олимпиада, 2003г.)

  3. Последовательность из 36 нулей и единиц начинается с 5 нулей. Среди пятёрок подряд стоящих цифр встречаются все 32 возможные комбинации. Найдите пять последних цифр последовательности.

  4. «Рыцари при дворе короля Артура» - теорема Дирака.

За круглым столом у короля Артура собрались 2n рыцарей, у каждого из которых не более (n–1) врага среди остальных. Доказать, что советник короля Мерлин может так рассадить рыцарей, что враги рядом не сядут. Сформулируйте теорему Дирака в общем виде.

  1. На конференцию приехало 2n человек, каждый из которых знаком не менее чем с n остальными. Докажите, что участников можно так расселить в двухместные номера, чтобы в каждом номере жили знакомые друг с другом люди.

  2. Дано n фишек нескольких цветов, причём фишек каждого цвета не более n/2. Докажите, что их можно расставить на окружности так, чтобы никакие две фишки одинакового цвета не стояли рядом.

  3. В федеративном государстве, состоящем из двух республик, каждые два города соединены дорогой с односторонним движением; при этом, двигаясь по дорогам, можно из любого города попасть в любой другой. Туристическое агентство «Гамильтон» предлагает n различных туристических маршрутов по городам первой республики и m – по городам второй (любой из этих маршрутов предполагает посещение каждого города республики ровно по одному разу и возвращение в исходный город, причем всё это – не выезжая за пределы республики). Докажите, что агентство «Гамильтон» могло бы предложить любознательным туристам не менее mn аналогичных туристических маршрутов по городам всей федерации.




Нажми чтобы узнать.

Похожие:

Гамильтонов граф icon Мультиграф  Ориентированный граф
Построить граф структуры управления вуза, проверить, оказался он деревом или нет
Гамильтонов граф iconЕго величество граф введение
С дворянским титулом «граф» эту тему связывает только общее происхождение от латинского слова «графио» пишу
Гамильтонов граф iconПримерная программа на основе Государственных стандартов Л. Е. Журова. Букварь, Вентана-Граф, 2011. Математика 1 класс 4
Иванов С. В., Кузнецова М. И, Петленко Л. В. и др. Русский язык. Ч. 1 М.: Вентана-Граф, 2011
Гамильтонов граф iconГрафы. Основные определения с примерами. Граф
Граф – это некоторое конечное множество точек, называемых вершинами, и конечный набор линий, называемых ребрами, соединяющих некоторые...
Гамильтонов граф iconГрафы. Основные определения с примерами. Граф
Граф – это некоторое конечное множество точек, называемых вершинами, и конечный набор линий, называемых ребрами, соединяющих некоторые...
Гамильтонов граф iconДія I
Ніч. Варта охороняє замок графа ді Луни. Феррандо розповідає, що коли граф ді Луна та його брат були ще немовлятами, до замку потрапила...
Гамильтонов граф iconУчебник для учащихся 1 класса общеобразовательных учреждений. 2-е изд., с уточн. М.: Вентана Граф, 2011
Безруких М. М. Прописи к учебнику «Букварь»: 1 класс: для учащихся общеобразоватльных учреждений. 3 ч. / М. М. Безруких, М. И. Кузнецова....
Гамильтонов граф icon1 Побудова гса по описах граф-схем, приведених в завданні до курсової роботи, побудуємо гса г
По описах граф-схем, приведених в завданні до курсової роботи, побудуємо гса г1-Г5 (мал. 1 5), додавши початкові І кінцеві вершини...
Гамильтонов граф iconМетодическое пособие для учителя. Химия 8-9 класс. М.: Вентана Граф, 2006 г. Н. Е. Кузнецова, Н. Н. Гара. Химия. 8 9 класс: Программы по химии,2006 год, Вентана Граф для учащихся
Н. Е. Кузнецова, Н. Н. Гара, рекомендованная Департаментом образовательных программ и стандартов общего образования Министерства...
Гамильтонов граф iconКал граф(1)

Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©rushkolnik.ru 2000-2015
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы