Сколько неориентированных графов есть на 3 вершинах?

Question

Неориентированный граф содержит 3 вершины. Сколько неориентированных графов можно сформировать? Я попробовал комбинацию, но ответ был неправильным.

Answer 1

граф с п вершинами может иметь до N*(N-1)/2 края (если петли Арен» t разрешено).

Таким образом, общее число возможных графиков составляет 2^(N*(N-1)/2).

Answer 2

Мой ответ 8 Графики: Для ненаправленного графика с любыми двумя узлами, не имеющими более одного края. График с N вершинами может иметь значение не более nC2 ребра. 3C2 is (3!)/((2!) * (3-2)!) => 3. Итак, вы можете вычислить число графов с 0 ребрами, 1 ребер, 2 ребрами и 3 ребрами.

В макс число ребер для N узлов = N * (N-1)/2 Поставляется с nC2 и для каждого ребра у вас есть возможность выбрать его в графике или не выбирать его, и с каждым вы получаете уникальный график, и он дает формулу: 2^(N * (N-1)/2) графики возможны.

Если узлы называются A, B, и С, затем

Все отключенные узлы: 0 край

a b c 

= 1 График

только 2 узлы, соединенные: 1 край

a--b c 
b--c a 
c--a b 

= 3 графы

все 3 узлов, соединенных: 2 ребра

a--b--c (c--b--a will be same) 
a--c--b (b--c--a will be same) 
b--a--c (c--a--b will be same) 

= 3 узлы

все 3 узлы, соединенные: 3 ребра

a--b--c--a 

= 1 График

Всего 8 Графики. Другой способ взглянуть на это для каждого края у вас есть 2 варианта либо иметь его, либо не иметь его там, сделав 2 поднятым до мощности 3 (2 варианта и 3 ребра), делая 8 в качестве ответа.

Для ориентированного графа мы будем иметь больше дел, чтобы рассмотреть, я пытаюсь ниже, чтобы найти число графиков, если мы могли бы Направленный граф (Обратите внимание, что ниже для случая, когда мы не имеем больше чем 1 край между узлами 2, в случае, если мы имеем больше чем 1 ребро между узлами 2, то ответ будет отличаться)

0 край

аЬс = 1 График

1 край

a-->b c 
a<--b c 
b-->c a 
b<--c a 
c-->a b 
c<--a b 

= 6 Графики

2 ребра

a-->b-->c 
a-->b<--c 
a<--b-->c 
a<--b<--c 
b-->a-->c 
b-->a<--c 
b<--a-->c 
b<--a<--c 
a-->c-->b 
a-->c<--b 
a<--c-->b 
a<--c<--b 

= 12 Графики

3 фронтам

a-->b-->c-->a 
a-->b-->c<--a 
a-->b<--c-->a 
a-->b<--c<--a 
a<--b-->c-->a 
a<--b-->c<--a 
a<--b<--c-->a 
a<--b<--c<--a 

= 8 Графики

Всего = 1 + 6 + 12 + 8 = 27 Графики

Answer 3

Сначала вы должны решить, хотите ли вы подсчитать с пометкой или немаркированных объектов. Предположим, что ваш график прост, то есть: нет циклов или нескольких ребер.

Если вы подсчитаете помеченные объекты, вы подсчитываете количество симметричных 0-1 матриц с 0s на диагонали (т. Е. Матрицы смежности графов). Существует 2^(1 + 2 ... + n-1) = 2^(n (n-1)/2) таких матриц, следовательно, такое же число неориентированных простых графов. При n = 3 это дает 2^3 = 8 графов.

Если вы считаете немеченым объектом, то вы подсчитываете количество графиков до изоморфизма графа. Это гораздо более сложный вопрос. Некоторые вычислительные данные доступны на веб-сайте Онлайн-энциклопедия целых последовательностей (OEIS) для более крупных n: https://oeis.org/A000088. На этом веб-сайте мы делаем вывод, что на 3 вершинах имеется 4 немаркированных графа (на самом деле: пустой граф, ребро, вишня и треугольник).