Теория графов: Основы и применения
Теория графов — это богатая область математики, изучающая свойства графов — математических структур, используемых для моделирования парных отношений между объектами. В данном контексте граф — это не привычный координатный график, а скорее совокупность вершин (или узлов), соединенных ребрами.
Основные понятия
Базовые определения
- Граф: Граф G = (V, E) состоит из множества V вершин и множества E ребер, где каждое ребро соединяет пару вершин.
- Вершина (Узел): Основная единица в графе, часто представляемая как точка или окружность.
- Ребро: Соединение между двумя вершинами, обычно изображаемое как линия.
- Смежные: Две вершины являются смежными, если они соединены ребром.
- Инцидентное: Ребро инцидентно вершине, если вершина является концом этого ребра.