Факультативные занятия по теме "Теория графов"

                                                                 Предмет математики настолько серьезен,

                                                                 что полезно не упускать случаев делать его

                                                                 немного занимательным.

                                                                                                            Б. Паскаль

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

              В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику.  Графы эффективно используются в теории планирования и управлении, теории расписаний, социологии, математической лингвистике, экономики, биологии, медицине. Широкое применение находят графы в таких  областях  прикладной математики, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач. Теория графов быстро развивается, находит все  новые  применения в различных  разделах  математики.

                В теории графов существуют  различные направления, одним  из них является раздел графов с цветными  рёбрами.

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

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

       СВОЙСТВА  ПОЛНЫХ  ГРАФОВ  С  ЦВЕТНЫМИ  РЁБРАМИ.

Задача 1. Шесть школьников участвуют в шахматном турнире, который проводится в один круг, т.е. каждый шахматист  встречается

со всеми участниками по одному разу. Доказать, что среди них всегда

найдутся три участника турнира, которые провели уже все встречи между собой или еще не сыграли друг с другом ни одной партии.

Решение:  Любые два участника турнира непременно находятся между собой в одном из двух отношений: они либо уже сыграли между собой, либо ещё не сыграли.

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