Donner le minimum et le nombre maximum d'arêtes dans un graphe connexe non orienté de n sommets?

serait minimale (n-1) arêtes?

Je ne suis pas sûr au sujet de maximum

OriginalL'auteur user2675364 | 2014-11-24

  1. 5

    Oui.. Le nombre minimum d'arêtes pour les non-orienté graphe connexe est (n-1) bords. Pour voir cela, puisque le graphe est connecté, alors il doit y avoir un chemin d'accès unique à partir de chaque sommet à tous les autres sommets et de retrait de tout bord vont rendre le graphique déconnecté.

    Pour le nombre maximum d'arêtes (en supposant que les graphes simples), chaque sommet est relié à tous les autres sommets qui donne surviennent pour n(n-1)/2 bords (utiliser la poignée de main lemme). D'une autre manière: regarder par-dessus K_n (le graphe complet à n sommets) qui a le nombre maximum d'arêtes.

    "la suppression de tout bord vont rendre le graphique déconnecté". Pourquoi?

    OriginalL'auteur Xline

  2. 2

    Demande: Si il y a N verticies, le Min est N-1 et le max est de N*(N-1)/2

    Preuve:

    Considérer une matrice de contiguïté, où les éléments sont soit 1 (pour indiquer la présence d'une arête) ou 0 (pour indiquer l'absence d'un bord). Pour un graphe d'être connecté, il doit y avoir au moins un "1" dans chaque ligne de la partie supérieure du triangle.

    La minimum est réalisé par seulement placer un 1 dans chaque ligne de la partie supérieure du triangle. Maintenant, si la matrice de contiguïté est N par N, la première ligne a N-1 éléments du triangle supérieur, le second a N-2 éléments dans le triangle supérieur, ..., et la dernière ligne est 0 éléments dans le triangle supérieur. C'est, il y a N-1 total des lignes "avec un triangle supérieur", chacun avec une seule 1. Par conséquent, le nombre d'arêtes dans N-1.

    La maximum se produit si tous les éléments de la partie supérieure du triangle a un. Maintenant, le nombre d'éléments dans le triangle supérieur de l'ensemble de la matrice est

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

    Pour la dernière égalité, souvenez-vous de votre calcul en cours " finis sommes. Veuillez voir la deuxième formule ici, et de remplacer "m" avec (N-1)": https://en.wikipedia.org/wiki/List_of_mathematical_series#Sums_of_powers

    PS: je souhaite vraiment que je pourrais utiliser le LaTeX sur LE!

    OriginalL'auteur RMurphy