Конспект на тему понятие графа связанный граф дерево цикл графа на плоскости

# Конспект: Теория графов ### 1. Понятие графа Граф — это математический объект, состоящий из двух множеств: * $V$ — множество вершин (узлов). * $E$ — множество ребер (связей), соединяющих пары вершин. Записывается как $G = (V, E)$. ### 2. Связанный граф Граф называется **связанным**, если между любыми двумя его вершинами существует путь. Если граф состоит из нескольких отдельных "кусков", он называется несвязанным. ### 3. Дерево Дерево — это связный граф, в котором нет циклов. * В дереве всегда на одно ребро меньше, чем вершин: $|E| = |V| - 1$. * Если добавить в дерево хотя бы одно ребро, обязательно появится цикл. ### 4. Цикл графа Цикл — это замкнутый путь. Если мы идем по ребрам графа и возвращаемся в ту же вершину, с которой начали, не проходя по одному и тому же ребру дважды, мы описали цикл. ### 5. Графы на плоскости (Планарные графы) Граф называется **планарным**, если его можно нарисовать на плоскости так, чтобы его ребра не пересекались (кроме как в вершинах). * Для связных планарных графов верна **формула Эйлера**: $V - E + F = 2$, где $F$ — количество граней (областей, на которые граф делит плоскость).