Тема: Введение в теорию графов.

Вопросы:

1. История возникновения теории графов.

2. Основные понятия теории графов.

3. Примеры использования теории графов.

1. История возникновения теории графов.

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

Такие схемы встречаются всюду под разными названиями: социограммы (в психологии), симплексы (в топологии), электрические цепи (в физике), диаграммы организации (в экономике), сети коммуникаций, генеалогические деревья и т.д.

Д.Кёниг, предложил называть такие схемы "графами" и систематически изучать их свойства.

В совершенно различных дисциплинах приходится использовать аналогичные теоремы; так, понятие "матрицы инциденций", введенное Кирхгофом для изучения электрических цепей, было привлечено А.Пуанкаре в топологию при создании его "analysis situs"; понятие "точки сочленения", с давних пор известное в социологии, впоследствии появилось в электронике; все примеры такого рода перечислить невозможно. Чтобы можно было применять теорию графов в столь разнообразных областях, она должна быть в высшей степени абстрактной и формализованной.

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

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

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

Эта теория тесно связана также со многими разделами математики, среди которых — теория групп, теория матриц, численный анализ, теория вероят­ностей, топология и комбинаторный анализ.

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

Теория графов «открывалась» независимо много раз: её с полным основанием можно считать разделом прикладной ма­тематики. В самом деле, наиболее раннее известное упоминание этой теории встречается в работах Эйлера, и хотя проблему, кото­рой он занимался, можно рассматривать как обычную головоломку, псе же она возникла из практики.

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

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

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