Comment prouver nombre max de connexion entre les n nœuds est n*(n-1)/2

Donné à n nœuds, chaque nœud est connecté à tous les autres noeuds (sauf lui-même) le nombre de connexions est n*(n-1)/2

Comment le prouver ?

Ce n'est pas des devoirs à faire à la question. J'ai été loin de la CS des livres de texte pour longtemps et ont oublié la théorie sur la façon de le prouver.

  • Cette question semble être hors-sujet parce que c'est à propos des mathématiques.
  • 4 upvotes, l'op s'excuse car il semble que des devoirs à faire à la question, puis quelqu'un dit que c'est hors-sujet parce que c'est sur les mathématiques. Vous avez obtenu d'aimer de la SORTE.
InformationsquelleAutor Manohar | 2012-12-05
  1. 14

    Et un de plus solution, la combinatoire:
    Le problème est équivalent au nombre de paires de nœuds dans le graphe, c'est à dire:

    Comment prouver nombre max de connexion entre les n nœuds est n*(n-1)/2

    InformationsquelleAutor SomeWittyUsername
  2. 26

    vous avez à n nœuds, chaque a n -1 connexions (chacun d'eux est relié à chaque nœud, sauf lui-même), nous obtenons donc n*(n-1). Toutefois, en raison de la connexion (x,y) et (y,x) est le même (pour toutes les connexions), nous nous retrouvons avec n*(n-1)/2.

    • because connection (x,y) and (y,x) is the same (for all connections), we end up with n*(n-1)/2. Merci, l'explication de cette intuition a été comme une bouffée d'air frais
    • Vous êtes accueilli
    InformationsquelleAutor Aram Gevorgyan
  3. 11

    Désolé pour la mauvaise nomenclature, je suis un des physiciens, pas un CS/Math guy.

    Chaque nœud unique (ce qui n'est n) doit être connecté à tous les autres. Il y a (n-1) "tout le monde".

    De sorte que chaque n nœuds ont n-1 des connexions venant d'eux. n(n-1)

    Mais étant donné que chaque connexion est "bidirectionnel" (a to b = b to a), vous vous retrouvez avec un facteur de 1/2

    donc n*(n-1)/2

    InformationsquelleAutor user1512321
  4. 2

    Preuve par induction. De la Base de cas - par 2 noeuds, il est 1 de connexion et 2 * 1 /2 == 1. Maintenant, en supposant que pour N nœuds, nous avons N * (N-1) /2 connexions. L'ajout d'un nœud a à établir N des connexions supplémentaires, et:

    N * (N-1) /2 + N =
(N^2 - N + 2N) /2 =
(N^2 + N) /2 =
(N + 1) * N /2

    Cette dernière ligne est exactement N * (N - 1) /2 avec N remplacé par N+1, de sorte que la preuve est bon.

    InformationsquelleAutor twalberg
  5. 1

    La degré de chaque sommet est n-1 (parce qu'il a n-1 voisins).

    La poignée de main lemme, dit: Sigma(deg(v)) (for each node) = 2|E|. Donc: 

    Sigma(deg(v)) (for each node) = 2|E|
Sigma(n-1) (for each node) = 2|E|
(n-1)*n = 2|E|
|E| = (n-1)*n /2

    CQFD

    InformationsquelleAutor amit
  6. 1

    pour le noeud 1: n connexion

    pour le nœud 2: n-1 connexions(déjà le premier nœud est connecté )

    pour 3 nœuds: n-2 connexions
    ..
    pour le nœud n: n-(n-1) connexions

    Par conséquent, le total des connexions = n + n-1 + n-2 + ........1

                            = n(n-1)/2 (sum of first n-1 natural numbers)
    InformationsquelleAutor rsirs
  7. 0

    La réponse la plus appropriée pour déterminer le nombre maximum de liens possibles à partir de N nœuds du réseau est...

    Le nombre total de combinaisons possibles/connexion où un lien nécessite 2 nœuds; donc:

    (N!) /[(N-2)!)(2!)] = N(N-1)(N-2)! / (N-2)!(2!);

    S
    o N(N-1) /2

    où N>1 car il faut 2 nœuds d'avoir un Lien.

    InformationsquelleAutor Dino
  8. 0

    Fin et pas une preuve, mais vous pouvez "visualiser" les nœuds que les coordonnées et les relations que les cellules dans une matrice je ne sais pas comment faire pour en tirer quelque chose ici.

    Une colonne par nœud, une ligne par nœud, de la cellule à la croix est la relation.

    Vous avez xx possible cellules. Mais, vous devez supprimer le topleft-bottomright les cellules de la diagonale (un nœud nœud peut être liée à elle-même). Ainsi, vous supprimez x cellules et ont seulement (xx-x) = x*(x-1) cellules restantes. Ensuite, la cellule (x,y) est le même lien que la cellule (y,x), donc vous pouvez supprimer la moitié des cellules restantes : x*(x-1)/2

    InformationsquelleAutor Francois Cerbelle