Теория графов - раздел математики, изучающий свойства графов. Наглядно граф можно представить как геометрическую конфигурацию, которая состоит из точек ( вершины ) соединенных линиями ( ребрами ).
G = (V, E), где V есть подмножество любой Счетное множества, а E - подмножество V × V.
Формальное определение графа:
Пусть X = {x 1, ..., X N } - некоторая конечное множество (множество вершин), M 2 - множество всех неупорядоченных пар элементов из X,
M 2 = {(X и, X J ): X и ∈ X, X J ∈ X, i ≠ j}
Граф G (X, W) - пара множеств X, W ⊂ M 2 . Множество X - это множество вершин, множество W - это множество ребер. Если (X и, X J ) ∈ W, то мы говорим, что ребро (X и, X J ) соединяет вершину X и с вершиной X J ; другая терминология - ребро (X и, X J ) и вершины X и и X J инцидентны.
Граф G (X, W) называется полным, если W = M 2 .
Если множество X содержит n вершин, то, очевидно, число ребер полного графа равна C N 2 . Полный граф с n вершинами обозначается K N .
Граф G (X, W) называется пустым, если W = ∅.
Вершины X и и X J графа G (X, W) инцидентны, если (X и, X J ) ∈ W.
Степенью d (X и ) вершины X и графа G (X, W) называется число вершин X J, которые инцидентны вершине X и (число отрезков, выходящих из вершины X и ).
Если d (X и ) = 1, то вершина X и называется конечной вершиной графа G (X, W). Если d (X и ) = 0, то вершина X и называется изолированной.
Связный граф называется эйлеровым графом, если существует замкнутый цепь, проходит через каждое ребро. Такая цепь называть эйлеровым цепью или эйлеровым циклом.
Граф называется напивейлеровим, если существует цепь, который проходит через каждое его ребро ровно один раз.
Лесом называется граф, не содержащий циклов. Связный лес называется деревом.
Плоским графом называется граф, в диаграмме которого линии, соответствующие ребрам, пересекаются в точках, соответствующих вершинам графа.
Планарным графом называется граф G, изоморфен некоторому плоскому графу. Последний называется плоской картой графа G.
Внутренней гранью плоского связного графа называется конечная область плоскости, ограниченная замкнутой маршруту графа и не содержит внутри ни вершин, ни ребер графа. Часть плоскости, которая состоит из точек, не принадлежащих одной внутренней грани, называется внешней гранью.
Множество всех граней плоского связного графа обозначается P. Замкнутый маршрут, ограничивающий грань, называется пределом грани, а длина этого маршрута - степенью грани. Степень грани сказывается Pr.
Максимальным планарным графом называется планарный граф, который при добавлении к нему любого ребра перестает быть планарным.
Плоский связный граф, каждая грань которого (включая внешнюю) ограничена треугольником, называется триангуляции.
Сегодня теория графов используется в стеклообрабатывающем оборудовании при раскройте стекла, пример можно посмотреть тут - столы для раскроя ламинированного стекла. Толчок к развитию теория графов получила на рубеже XIX и ХХ веков, когда резко возросло количество работ в области топологии и комбинаторики, с которыми ее связывают тесные узы родства. Как отдельная математическая дисциплина, представлена в работе математика Кенига в 30-е годы XX века.
