Сколько ребер может иметь унипатический граф?

19

Унипатический граф - это ориентированный граф, такой, что существует не более одного простого пути от любой вершины к любой другой вершине.

Унипатические графы могут иметь циклы. Например, двусвязный список (а не круговой!) Является унипатическим графом; если список имеет элементов, граф имеет n - 1 циклов длины 2, всего 2 ( n - 1 ) .nn12(n1)

Каково максимальное число ребер в унипатическом графе с вершинами? Подойдет асимптотическая оценка (например, O ( n ) или Θ ( n 2 ) ).nO(n)Θ(n2)

Вдохновленный Находить кратчайшие пути в взвешенном унипатическом графе ; в своем доказательстве я сначала хотел заявить, что число ребер было но затем понял, что достаточно ограничить количество циклов.O(n)

Жиль "ТАК - перестань быть злым"
источник
Хороший вопрос Мы должны попытаться улучшить либо вашу нижнюю границу, либо мою верхнюю границу :).
РБ

Ответы:

12

Unipathic граф может иметь ребра. Там очень хорошо известный вид графа , что это unipathic и имеет п 2 / 4 ребер.Θ(n2)n2/4

Рассмотрим полный двудольный граф с ориентированными ребрами . Этот граф унипатичен и не имеет цикла: все его пути имеют длину 1 . Он имеет 2 м вершин и м 2 ребер.(i,j)[1,m]2,aibj12mm2

(Дополнительный вопрос: является ли это соотношение максимальным? Вероятно, нет, но у меня нет другого примера. Этот пример является максимальным в том смысле, что любое ребро, которое вы добавляете между существующими узлами, нарушит унипатическое свойство.)

Жиль "ТАК - перестань быть злым"
источник
«Любое ребро, которое вы добавляете между существующими узлами, нарушит унипатическое свойство». Как добавление ребра нарушит свойство? b1a1
Митч
@mitchus a2b1a1b2
Жиль "ТАК - перестань быть злым"
1
Я думаю, что мой разум был как-то унипатичен в тот день :) Что касается максимальности, соотношение может увеличиться до 1/4 для больших n , но для у двусвязного списка больше ребер, чем п 2 / 4 . n{2,3,4,5,6}n2/4
Митч
0

Я не знаю, есть ли унипатический граф на более чем ребра, но вот аргумент, показывающий, что не болееn2n24Возможно 2 +3ребра:n22+3

G=(V,E)|E|n22+3

vV

din(v)n2+1

U={uV(u,v)E}

Обратите внимание , что если существует вершина такое , что U 1xV{v}

u1u2U:(x,u1),(x,u2)E

(xu1v)(xu2v)

Это означает, что (добавление ребер из {v}×U

|E(V×U)|2|U|

Таким образом, средняя степень вершин превосходит 2, поэтому: | E | = | E ( V × U ) | + | E ( V × ( V U ) ) |U

|E|=|E(V×U)|+|E(V×(VU))|
2|U|+n|VU|2(n2+1)+n(n21)<n22+3

RB
источник