С четырьмя вершинами сколько можно построить различных графов?

Если у нас есть четыре вершины, то количество возможных графов, которые можно построить, зависит от того, какие именно рёбра могут быть проведены между вершинами. В теории графов существует два основных случая: ориентированные и неориентированные графы. Рассмотрим оба случая:

1. Неориентированные графы

В неориентированном графе рёбра не имеют направления, то есть, если между вершинами $A$ и $B$ проведено ребро, то это одно и то же, что и между $B$ и $A$. Чтобы понять, сколько существует различных неориентированных графов, нужно подсчитать возможные рёбра между четырьмя вершинами.

Для четырёх вершин возможные рёбра между ними — это все пары вершин. Количество таких пар вычисляется по формуле для сочетаний:

Это означает, что между четырьмя вершинами может быть максимум 6 рёбер. Каждое из рёбер может быть либо присутствовать, либо отсутствовать в графе. Следовательно, для каждого из 6 рёбер есть 2 возможных состояния: оно либо есть, либо его нет. Это даёт нам:

Таким образом, для четырёх вершин существует 64 различных неориентированных графа.

2. Ориентированные графы

В ориентированном графе рёбра имеют направление, то есть, если есть рёбра $A \to B$ и $B \to A$, это два разных рёбра. Для четырёх вершин количество возможных направленных рёбер между ними равно количеству всех возможных упорядоченных пар вершин. Поскольку у нас есть 4 вершины, количество таких рёбер будет равно:

Это количество рёбер, так как от каждой вершины можно провести ребро к 3 остальным вершинам. Как и в случае с неориентированным графом, каждое из рёбер может быть либо присутствовать, либо отсутствовать. Следовательно, для каждого из 12 рёбер есть 2 возможных состояния:

Таким образом, для четырёх вершин существует 4096 различных ориентированных графов.

Итог:

• Для четырёх вершин можно построить 64 неориентированных графа.

• Для четырёх вершин можно построить 4096 ориентированных графов.