Унипатический граф - это ориентированный граф, такой, что существует не более одного простого пути от любой вершины к любой другой вершине.
Унипатические графы могут иметь циклы. Например, двусвязный список (а не круговой!) Является унипатическим графом; если список имеет элементов, граф имеет n - 1 циклов длины 2, всего 2 ( n - 1 ) .
Каково максимальное число ребер в унипатическом графе с вершинами? Подойдет асимптотическая оценка (например, O ( n ) или Θ ( n 2 ) ).
Вдохновленный Находить кратчайшие пути в взвешенном унипатическом графе ; в своем доказательстве я сначала хотел заявить, что число ребер было но затем понял, что достаточно ограничить количество циклов.
graphs
combinatorics
Жиль "ТАК - перестань быть злым"
источник
источник
Ответы:
Unipathic граф может иметь ребра. Там очень хорошо известный вид графа , что это unipathic и имеет п 2 / 4 ребер.Θ ( н2) N2/ 4
(Дополнительный вопрос: является ли это соотношение максимальным? Вероятно, нет, но у меня нет другого примера. Этот пример является максимальным в том смысле, что любое ребро, которое вы добавляете между существующими узлами, нарушит унипатическое свойство.)
источник
Я не знаю, есть ли унипатический граф на более чем ребра, но вот аргумент, показывающий, что не болееn2N24 Возможно 2 +3ребра:N22+ 3
Обратите внимание , что если существует вершина такое , что ∃ U 1x ∈ V∖ { v }
Это означает, что (добавление ребер из{v}×U
Таким образом, средняя степень вершин превосходит 2, поэтому: | E | = | E ∩ ( V × U ) | + | E ∩ ( V × ( V ∖ U ) ) |U
источник