Quel est le nombre maximum de bords dans un graphique dirigé avec n n des nœuds?

Question

Quel est le nombre maximum de bords dans un graphique dirigé avec n n des nœuds? Y a-t-il une limite supérieure ?

Answer 1

Si vous avez des nœuds, il ya des bords dirigés que peut conduire à partir de lui (allant à tous les autres nœuds). Par conséquent, le nombre maximum de bords est `` .

Answer 2

Dans un graphique non dirigé (à l'exclusion des multigraphes), la réponse est n '(n-1)/2. Dans un graphique dirigé, un bord peut se produire dans les deux directions entre deux nœuds, puis la réponse est nô(n-1).

Answer 3

Si le graphique n'est pas un graphique multi alors il est clairement n ' (n - 1), comme chaque nœud peut tout au plus avoir des bords à tous les autres nœuds. S'il s'agit d'un multigraphe, il n'y a pas de limite maximale.

Answer 4

Il peut y avoir autant de `` bords dans le graphique si ce n'est pas multi-bord est autorisé.

Et c'est réalisable si nous étiquetons les vertiges et il ya un avantage de ```` l'iff .

Voir ici.

Answer 5

Non dirigé est N '2. Simple - chaque nœud a des options N de bords (lui-même inclus), total de nœuds N donc N N