Geben Sie die minimale und maximale Anzahl von Kanten in einem ungerichteten verbundenen Graphen von n Knoten an.

Question

wäre Minimum (n-1) Kanten?

Ich bin nicht sicher über maximal

Answer 1

Ja .. Die minimale Anzahl von Kanten für ungerichtete verbundenen Graphen (n-1) Kanten ist. Um dies zu sehen, muss, da der Graph verbunden ist, ein eindeutiger Pfad von jedem Eckpunkt zu jedem anderen Eckpunkt vorhanden sein und das Entfernen einer Kante wird den Graphen trennen.

Für die maximale Anzahl von Kanten (unter der Annahme einfacher Graphen) ist jeder Eckpunkt mit allen anderen Eckpunkten verbunden, was für n(n-1)/2 Kanten entsteht (Handshaking-Lemma verwenden). Ein anderer Weg: Schauen Sie über K_n (der vollständige Graph mit n Ecken), der die maximale Anzahl von Kanten hat.

Answer 2

Claim: Wenn es N verticies sind, die Min ist N-1 und der max ist N * (N-1)/2

Beweis:

eine Adjazenzmatrix Man betrachte, wo der Elemente sind entweder 1 (um das Vorhandensein einer Kante anzuzeigen) oder 0 (um die Abwesenheit einer Kante anzuzeigen). Damit ein Graph verbunden wird, muss in jeder Zeile des oberen Dreiecks mindestens eine "1" vorhanden sein.

Das Minimum wird erreicht, indem nur eine 1 in jede Reihe des oberen Dreiecks platziert wird. Wenn nun die Adjazenzmatrix N mal N ist, hat die erste Reihe N-1 Elemente im oberen Dreieck, die zweite hat N-2 Elemente im oberen Dreieck, ... und die letzte Reihe hat 0 Elemente im oberen Dreieck. Das heißt, es gibt N-1 Gesamtzeilen "mit einem oberen Dreieck", jeweils mit nur einer 1. Daher die Anzahl der Kanten in N-1.

Die maximale tritt auf, wenn jedes Element des oberen Dreiecks eine Eins hat. Nun ist die Anzahl der Elemente im oberen Dreieck der gesamten Matrix

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

Für die letzte Gleichheit, rufen Sie die endlichen Summen Ihrer Kalkülkurse auf. Bitte beachten Sie die zweite Formel hier, und ersetzen Sie „m“ mit (N-1) ": https://en.wikipedia.org/wiki/List_of_mathematical_series#Sums_of_powers

PS: Ich wünschte wirklich, ich LaTeX verwenden könnte auf SO