Основные понятия теории графов. Гладких О.Б - 8 стр.

мостов, а при наличии областей с нечетным чис-     Составить их матрицы смежности. Найти граф
лом мостов мы будем располагаться в одной из       G=(G1 ® G2) ­ G3 и построить его диаграмму.
них. Продолжая двигаться так далее, пройдем че-    9. Даны графы своими матрицами смежности
рез все мосты по одному разу.
      В заключение отметим, что задача о Кенигс-
бергских мостах и подобные ей задачи вместе с
совокупностью методов их исследования состав-
ляют очень важный в практическом отношении
раздел математики, называемый теорией графов.      Найти матрицу смежности графа
Первая работа о графах принадлежала Л. Эйлеру и                  G = (G1 ® G3) ­ (G2 ® G3)
появилась в 1736 году. В дальнейшем над графами    и построить его диаграмму.
работали Кениг (1774-1833), Гамильтон (1805-       10. Для четырех графов найти: дополнение, число-
1865), из современных математиков – К. Берж, О.    вые характеристики, объединение графов a и d,
Оре, А. Зыков.                                     пересечение графов b и d, композицию графов c и
      Впоследствии теория графов стала исполь-     d.
зоваться в топологии, алгебре, теории чисел. В
наше время теория графов находит применение в
самых разнообразных областях науки, техники и
практической деятельности. Она используется при
проектировании электрических сетей, планирова-
нии транспортных перевозок, построении молеку-
лярных схем. Применяется теория графов также в
экономике, психологии, социологии, биологии.




                          8                                                 169