Graphentheorie / Schlichter ungerichteter Graph

Aufrufe: 43     Aktiv: 06.06.2021 um 23:58

0

Hallo, 

kann mir jemand sagen wie sich das begründen lässt warum die Anzahl der Kanten von einem schlichten ungerichteten Graphen sich durch diese Formel berechnen lässt:  |E| = n über 2 = n*(n-1) / 2. 

Würde mich über eure Hilfe freuen!

Diese Frage melden
gefragt

Punkte: 10

 

Kommentar schreiben

1 Antwort
0
Das kann Dir keiner sagen, weil es nicht stimmt. Da lassen sich leicht Gegenbeispiele finden. Schau nochmal nach, was in Deiner Quelle genau steht.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 14.12K
 

Warum sollte es nicht stimmt? Das ist die Formel wie man die Anzahl der Kanten für einen ungerichteten Graphen ohne Schlingen berechnet... Steht überall im Internet so.   ─   userfaece3 06.06.2021 um 22:56

https://de.universaldenker.org/argumentationen/332#:~:text=Ein%20ungerichteter%20Graph%20(ohne%20Schlingen,n%20%E2%88%92%201%20)%202%20Kanten.   ─   userfaece3 06.06.2021 um 22:57

Dann lies nochmal richtig Deine Quelle. Da steht nämlich "höchstens", sogar kursiv, damit es keiner übersieht. Und das stimmt allerdings auch.   ─   mikn 06.06.2021 um 23:02

Ich verstehe jetzt nicht ganz was Du genau meinst? Die Formel steht für HÖCHSTENS n*(n-1) / 2. Ich will ja jetzt nur wissen warum diese Formel gilt oder wie man da drauf kommt, mehr nicht.   ─   userfaece3 06.06.2021 um 23:07

In Deiner Frage ganz oben steht kein "höchstens" und daher ist die Aussage in Deiner Frage falsch. Nicht mehr und nicht weniger hab ich gesagt.
Willst Du wissen, warum die Aussage mit "höchstens" stimmt? Auf der von Dir verlinkten Seite ist ja ein Beweis.
  ─   mikn 06.06.2021 um 23:13

Ja bitte, das wäre tatsächlich noch interessant zu wissen, warum es mit "höchstens" gilt. :-)   ─   userfaece3 06.06.2021 um 23:16

Ein viel einfacherer Beweis als auf der von Dir verlinkten Seite ist bei wikipedia zu finden. Ein Graph kann nicht mehr Kanten haben als ein vollständiger Graph, und dann
https://de.wikipedia.org/wiki/Kantenzahl#Vollst%C3%A4ndige_Graphen
  ─   mikn 06.06.2021 um 23:20

Also müsste es eher lauten, dass die Anzahl der Kanten eines ungerichteten Graphen |E| <= n*(n-1) / 2 sein muss, oder?   ─   userfaece3 06.06.2021 um 23:26

1
Natürlich, "höchstens soundsoviel" bedeutet "\(\le\) soundsoviel", so steht es auch überall und das stimmt ja auch.
  ─   mikn 06.06.2021 um 23:32

Aso, ja das macht wirklich mehr Sinn. Vielen Dank für Deine Hilfe! :)   ─   userfaece3 06.06.2021 um 23:58

Kommentar schreiben