Эйлеров и полуэйлеров графы

Оглавление

Введение…………………………………………………………………………………2

Глава 1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ4

1.1 Понятие графа.Определение понятия графа4

1.2 Основные понятия, связанные с графом6

1.3 Примеры графов……………………………………………………………………8

Глава 2 Эйлеров и полуэйлеров графы13

2.1 Определение эйлерова и полуэйлерова графа. Примеры 13

2.2 Решение задачи Эйлера о семи кёнигсбергских мостах 13

2.3 Необходимые и достаточные условия для эйлеровых и полуэйлеровых графов…………………………………………………………………………………..16

Глава 3.ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ К РЕШЕНИЮ ЗАДАЧ ПО МАТЕМАТИКЕ………………………………………………………………………..18

3.1 Понятие графа……………………………………………………………………18

3.2 Степени вершин и подсчёт рёбер графа…………………………………………21

3.3 Связность графа……………………………………………………………………24

3.4 Графы Эйлера………………………………………………………………………25

ЗАКЛЮЧЕНИЕ………………………………………………………………………..30

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ……………………………….....31

ВВЕДЕНИЕ

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л.Эйлеру, появилась в 1736г. Вначале теория графов казалась довольно незначительным разделом математики, так как она имела дело в основном с математическими развлечениями и головоломками. Однако дальнейшее развитие математики и особенно её приложений дало сильный толчок развитию теории графов. Уже в XIX столетии графы использовались при построении схем.Решение многих математических задач упрощается, если удается использовать графы. Представление данных в виде графа придает им наглядность и простоту.Многие математические доказательства также упрощаются, приобретают убедительность, если пользоваться графами.Примерами графов могут служить схема метрополитена, схемы железных или шоссейных дорог, структурные формулы молекул, планы выставок и т. д., словом, схемы и планы (или карты) без указания масштабов, показывающие лишь связи между принадлежащими им объектами.В настоящее время теория графов находит многочисленное применение в разнообразных практических вопросах: при установлении разного рода соответствий, при решении транспортных задач, задач о потоках в сети нефтепроводов, в программировании и теории игр, теории передачи сообщений. Теория графов теперь применяется и в таких областях, как экономика, психология и биология.Цель работы: изучение эйлеровых графов и ихприменение к решению задач по математике. В этой работе мы познакомимся с понятием графа, подробнее рассмотрим эйлеровы графы, основные сведения и теоремы, связанные с этим понятием. А также задачи, которые решаются с помощью графов, в частности, эйлеровых.Тема работы актуальна, так как полученные знания могут использоваться при решении олимпиадных задач, а также задач, предлагаемых в математических конкурсах.

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

«Алгебра 9 класс» под редакцией С. А. Теляковского, издательство «Просвещение», Москва, 2010 г.

Белов, В.В. Теория графов / В.В. Белов, Е.М. Воробьев, В.Е. Шаталов. – М.: ВШ, 1976.

Березина, Л.Ю. Графы и их применение: популярная книга для школьников и преподавателей / Л.Ю. Березина. – Изд. 2-е, испр. и доп. – Москва: ЛИБРОКОМ, 2009. – 146 с.

В.М. Бондарев, В.И. Рублинецкий, Е.Г. Качко. Основы программирования, 1998 г.

Горбачев Н.В. Сборник олимпиадных задач по математике. - М.: МЦНМО, 2004. - 560 с.

Голованёва Л.В. Графы. Применение графов к решению задач«Графы и их применение» Л. Ю. Березина, издательство «Просвещение», Москва, 1979 г.

Емеличев В.А. Лекции по теории графов. - М.: Наука, 1990.- 384 с

Кузнецов, О.П. Дискретная математика для инженера /О.П. Кузнецов. 6-е изд., – СПб: «Лань», 2014. – 400 с.

Молчанов, В.А. Дискретная математика: учебное пособие / В.А. Молчанов. Саратов, 2013. 132 с.

Н. Кристофидес. Теория графов: алгоритмический подход, Мир, 1978 г.

Новиков, Ф.А. Дискретная математика для программистов: учебник для вузов / Ф.А. Новиков. – 3-е изд. – М. [и др.]: Питер, 2009.

О. Оре. Теория графов, Наука, 1982 г.Уилсон Р. Введение в теорию графов. - М.: Мир, 1977.- 207 с..

Уилсон, Р. Дж. Введение в теорию графов / Р. Дж. Уилсон. – М.: 1977.

Ф.А. Новиков. Дискретная математика для программистов, Питер, 2001 г.