Граф как структура вершин и ребер, связывающих вершины
Модель реальных дискретных задач
Определение \(G = (V, E)\)
Виды графов: простой, ориентированный, мультиграф (кратные ребра), псевдограф (кратные ребра и петли), гиперграф (ребра из нескольких вершин), конечные и бесконечные
Отношения смежности вершин и ребер и инцидентности вершины и ребра
Окружение \(N(v)\) и степень \(\deg v\) вершины
Подграф
Маршруты: цепь (разные ребра), цикл, простая цепь (разные вершины)
Расстояние в графах
Свойство связности
Изоморфизм графов
Представление графа: диаграмма, список ребер, списки смежности, матрица смежности, матрица инцидентности