Графы - математические объекты.
Теория графов применяется в таких областях, как физика, химия, теория связи, проектирование ЭВМ, электротехника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология.
Эта теория тесно связана также со многими разделами математики, среди которых теория групп, теория матриц, численный анализ, теория вероятностей, топология и комбинаторный анализ.
Единого общепринятого определения графа нет. В зависимости от решаемой задачи принимается то или иное определение, которые похожи, но это не одно и то же.
Теория графов родилась на берегах Невы, в Санкт-Петербурге, и основоположником является Леонард Эйлер, публиковавший в 1736 решение задачи о Кенигсбергских мостах.
1736 год. Эйлер доказывает, что задача о Кёнигсбергских мостах не имеет решения. Центральная часть Калининграда – это два берега реки Перголя и два острова этой реки. Острова соединены между собой мостом и у одного острова 2+2 моста с берегами и у другого 1+1. Всего 7 мостов. Задача: обойти все четыре части суши – два берега и два острова, пройдя по каждому мосту по одному разу.
Следующие шаги в развитии теории графов принадлежат Г. Кирхгофу, применившему теорию графов в 1847 г. к теории электрических цепей и А. Келли, разработавшему в 1857 г. теорию деревьев и применившему ее к теории химических изомеров.
1930 год. Казимир Куратовский доказывает, что задача о трех домах и колодцах не имеет решения. Имеется три дома и три колодца. Нужно проложить тропика от каждого дома к каждому колодцу так, чтобы они не пересекались.
Родившись при решении головоломок и занимательных задач, в XX веке теория графов стала мощным средством решения проблем многих наук, широкая приложимость стала дополнительным стимулом ее бурного развития. Сам термин "граф" ровно на 200 лет моложе этой теории, он введен в употребление в 1936 г. выдающимся венгерским математиком Д. Кенигом.
1976 год. Аппель и Хейкен с помощью компьютера, перебрав около 2000 контр-вариантов показали, что достаточно 4-ёх красок для раскраски карты. Карта – это разбивка поверхности не пересекающимися областями.