Для графа G = (V, E) докажите, что e ‹= n(n-1)/2 для всех n

Я пытаюсь решить эту проблему: для графа G = (V, E) докажите, что e ‹= n(n-1)/2 для всех n, где e — количество ребер, а n — число вершин.

Я думаю, что мне следует каким-то образом использовать математическую индукцию, чтобы выяснить правильный ответ, и использовать n = 1 или 0 для моей гипотезы, но я немного застрял на том, что делать после -- если я предположу, что n = k , тогда: e ‹= (k+1)k/2. и если n = k+1, то e ‹= k(k-1)/2.

Насколько я понимаю, из каждой вершины выходит n-1 возможных ребер, и всего n вершин, откуда берется n(n-1), а деление на 2 избавляет от повторов. Но я не знаю, как мне это доказать.


graph graph-theory proof
person winsticknova    schedule 12.01.2016    source источник
comment
Попробуйте Math Overflow вместо StackOverflow.   -  person geekazoid    schedule 12.01.2016
comment
Подсказка: n(n-1)/2 — это особое число: это сумма всех натуральных чисел от 1 до n — 1.   -  person John Bollinger    schedule 12.01.2016

Ответы (1)


arrow_upward
0
arrow_downward

Утверждение неверно для мультиграфов. Возьмите график:

 /---\
O-----O

Есть две вершины (O) и два ребра; поэтому n=2,e=2 и подстановка в n(n-1)/2 <= e дает 1 <= 2, что неверно.

Однако, если вы ограничите граф простотой — запретите ребра с петлями (где оба конца ребра заканчиваются в одной и той же вершине), множественные ребра (где два ребра соединяют одну и ту же пару вершин) и что граф ненаправленный — тогда свойство сохраняется.

Рассмотрим полный граф K_n (с n вершинами): каждая из n вершин инцидентна другим n-1 вершинам через соединительное ребро, поэтому имеется n(n-1) соединений из одной вершины в другую; учитывая, что ребра ненаправлены, каждое ребро будет подсчитываться дважды (т. е. считать от вершины A до вершины B и наоборот), тогда общее количество ребер будет n(n-1)/2.

Любой граф G_n (с n вершинами) будет подграфом K_n (поскольку вы не можете добавить больше ребер к K_n без создания мульти- или зацикленных ребер), тогда в G_n должно быть столько же или меньше ребер, чем в K_n.

Таким образом, e <= n(n-1)/2 для всех простых графов.

Если вы дополнительно ограничите график планарностью, вы можете указать, что e <= 3n - 6 (когда n > 2).

person MT0    schedule 14.01.2016