Наблюдения на графике

График представляет собой нелинейную структуру данных, используемую для представления набора объектов, где некоторые пары объектов связаны. Взаимосвязанные объекты представлены точками, называемыми вершинами , а линии, соединяющие вершины, называются ребрами . Вершины представлены буквой V , а ребра представлены буквой E. Можно также сказать, что граф — это пара множеств (V, E) . Например:

На приведенном выше графике множество вершин V = {0, 1, 2, 3} и множество ребер E = {(0, 1), (0, 3), (1, 2), (1, 3 ), (2, 3)} .

Вот некоторые наблюдения над графиком:

• Максимальное количество ребер в неориентированном графе из N вершин без учета циклов: Поскольку каждый узел может соединиться со всеми другими узлами, первый узел может соединиться с (N — 1) узлами . Второй узел может подключаться к (N – 2) узлам и так далее. Следовательно,

The total number of edges are: 1 + 2 + 3 + ··· + N = N*(N – 1)/2 edges

• Максимальное количество ребер в ориентированном графе из N вершин без учета петель: Каждое ребро имеет свою начальную вершину и конечную вершину. Есть N вариантов начальной вершины. Поскольку циклов нет, есть (N – 1) вариантов конечной вершины. Таким образом, умножая эти варианты вместе, мы подсчитываем все возможные варианты. Следовательно,

The total number of edges are: N*(N – 1)

• Максимальное количество ребер в графе с N вершинами с петлей:

The total number of edges are: N*N

• Минимальное количество ребер в неориентированном графе с N вершинами: поскольку граф связан, должен быть уникальный путь от каждой вершины к любой другой вершине, и удаление любого ребра сделает граф несвязным. Минимум достигается размещением 1 в каждой строке верхнего треугольника. Теперь, если матрица смежности имеет размерность NxN , первая строка имеет (N – 1) элементов в верхнем треугольнике, вторая имеет (N – 2) элементов в верхнем треугольнике, и так далее. и последняя строка имеет 0 элементов в верхнем треугольнике. То есть всего (N – 1) строк «с верхним треугольником», в каждой всего 1 . Следовательно,

The total number of edges are: (N – 1)

• Количество матриц смежности, возможное для невзвешенного графа с N вершинами и E ребрами: Для невзвешенного графа с N вершинами он может быть представлен как (NxN) матрица (двумерный массив), где каждое значение равно 0 (что обозначает -существование ребра) или 1 (что означает наличие ребра).

Теперь, если в первой строке есть N различных вариантов , во второй строке есть (N – 1) вариантов (так как информация о ребрах 1, 2 известна) и так далее. Таким образом, общие возможности:

N*(N – 1)*(N – 2)* … *1 = N!

Или можно сказать, что оно равно количеству перестановок N элементов, т.е. N! .

• Количество возможных списков смежности для графа с N вершинами и E ребрами: Аналогично объяснению выше. Оно равно количеству перестановок ребер, т.е. E! .
• Пусть G — граф, в котором все вершины имеют степень не менее двух. Тогда G содержит цикл: предположим, что G проста, и пусть P будет самым длинным путем как (v ₀ v ₁ v ₂ … v _a−1 v _a ) . Поскольку известно, что степень v _a > 2 , v _a должна быть смежной по крайней мере с одной вершиной v , которая не является (v _a – 1) , если v ∉ {v ₀ , …, v _{a − 2} } , тогда он мог бы расширить путь P до v . Однако P был выбран максимальной длины, так что это невозможно, и, следовательно, v ∈ {v ₀ …, v _{a – 2} } . Таким образом, если v = v _i , то v _i+1 , …, v _a, v _i является циклом.
• Формула Кэли:

For N ≤ 1, there are precisely N^{N – 2} tree graphs on N-la belled vertices.