Grad (Graphentheorie)

Ein Diagramm mit einer Schleife mit Scheitelpunkten, die nach Grad gekennzeichnet sind

Im Graphentheorie, das Grad (oder Wertigkeit) von a Scheitel von a Graph ist die Anzahl von Kanten das sind Vorfall zum Scheitelpunkt; in einem Multigraph, a Schleife trägt 2 zum Grad eines Scheitelpunkts für die beiden Enden der Kante bei.[1] Der Grad eines Scheitelpunkts ist bezeichnet oder . Das maximaler Grad einer Grafik , bezeichnet durch , und die Mindestgrad einer Grafik, gekennzeichnet durch , sind das Maximum und das Minimum der Eckpunkte. In dem rechts gezeigten Multigraph beträgt der maximale Grad 5 und der Mindestgrad 0.

In einem Regelmäßige Grafik, jeder Scheitelpunkt hat den gleichen Abschluss, und so können wir davon sprechen das Grad der Grafik. EIN Komplette Graph (bezeichnet , wo ist die Anzahl der Scheitelpunkte im Diagramm) ist eine spezielle Art von regulärem Diagramm, in dem alle Scheitelpunkte den maximal möglichen Abschluss haben. .

In einem Signiertes Diagrammdie Anzahl der mit dem Scheitelpunkt verbundenen positiven Kanten wird genannt positiver Grad und die Anzahl der vernetzten negativen Kanten hat den Anspruch negativer Grad.[2][3]

Handshaking -Lemma

Hauptartikel: Handshaking -Lemma

Das Abschlusssumme gibt an, dass bei einer Grafik Anwesend

.

Die Formel impliziert, dass in jedem ungerichteten Graphen die Anzahl der Scheitelpunkte mit ungerem Grad gleichmäßig ist. Diese Aussage (sowie die Gradsummenformel) ist als die bekannt Handshaking -Lemma. Der letztere Name ergibt sich aus einem beliebten mathematischen Problem, nämlich zu beweisen, dass in jeder Gruppe von Menschen die Anzahl der Menschen, die mit einer seltsamen Anzahl anderer Personen aus der Gruppe die Hände geschüttelt haben, die Hände geschüttelt haben.

Gradsequenz

Zwei nicht iisomorphe Graphen mit derselben Gradsequenz (3, 2, 2, 2, 2, 1, 1, 1).

Das Gradsequenz einer ungerichteten Grafik ist die nicht erhöhte Sequenz seines Scheitelpunktgrades;[4] Für das obige Grafik ist es (5, 3, 3, 2, 2, 1, 0). Die Gradsequenz ist a Diagramminvariante, Also isomorphe Graphen haben die gleiche Gradsequenz. Die Gradsequenz identifiziert jedoch im Allgemeinen keine Grafik. In einigen Fällen haben nicht iisomorphe Graphen die gleiche Gradsequenz.

Das Gradsequenzproblem ist das Problem, einige oder alle Grafiken zu finden, wobei die Gradsequenz eine gegebene nicht steigende Sequenz positiver Ganzzahlen ist. (Nachfoling -Nullen können ignoriert werden, da sie durch Hinzufügen einer geeigneten Anzahl isolierter Eckpunkte in die Grafik trivial realisiert werden.) Eine Sequenz, die die Gradsequenz einiger Graphen ist, d. H. Für die Gradsequenzprobleme eine Lösung hat, heißt a Grafik oder Grafische Sequenz. Infolge der Gradsummenformel kann jede Sequenz mit einer ungeraden Summe, wie (3, 3, 1), nicht als Gradsequenz eines Graphen realisiert werden. Die Inverse ist auch wahr: Wenn eine Sequenz eine gleichmäßige Summe hat, ist es die Gradsequenz eines Multigraphen. Die Konstruktion eines solchen Diagramms ist unkompliziert: Schließen Sie die Eckpunkte mit ungeraden Graden an (bilden Sie a Matching) und füllen Sie die verbleibenden Gradzahlen durch Selbstschleifen aus. Die Frage, ob eine bestimmte Abschlusssequenz durch a realisiert werden kann Einfaches Diagramm ist schwieriger. Dieses Problem wird auch genannt Diagrammrealisierungsproblem und kann durch beide gelöst werden ERDőS -Gallai Theorem oder der Havel -Hakimi -Algorithmus. Das Problem der Suche oder Schätzung der Anzahl der Diagramme mit einer bestimmten Gradsequenz ist ein Problem aus dem Gebiet von Graph -Aufzählung.

Allgemeiner die Gradsequenz von a Hypergraph ist die nicht erhöhte Sequenz seiner Scheitelpunkte. Eine Sequenz ist -Grafik Wenn es die Gradsequenz einiger ist -uniform Hypergraph. Insbesondere a -Graphische Sequenz ist grafisch. Entscheidung, ob eine bestimmte Sequenz ist -Graphik ist machbar in Polynomzeit zum über die ERDőS -Gallai Theorem aber ist NP-Complete für alle (Deza et al., 2018 [5]).

Besondere Werte

Ein ungerichteter Diagramm mit Blattknoten 4, 5, 6, 7, 10, 11 und 12
  • Ein Scheitelpunkt mit Grad 0 wird als eine genannt Isolierter Scheitelpunkt.
  • Ein Scheitelpunkt mit Grad 1 wird als Blattscheitel- oder Endscheitelpunkt oder ein Anhängerscheitelpunkt bezeichnet, und der mit diesem Scheitelpunkt fällige Rand wird als Anhängerkante bezeichnet. In der Grafik rechts ist {3,5} eine Anhängerkante. Diese Terminologie ist bei der Studie von häufig Bäume in der Graphentheorie und vor allem Bäume wie Datenstrukturen.
  • Ein Scheitelpunkt mit Abschluss n- 1 in einer Grafik auf n Scheitelpunkte heißt a dominierender Scheitelpunkt.

Globale Eigenschaften

  • Wenn jeder Scheitelpunkt des Diagramms den gleichen Grad hatk, Die Grafik wird a genannt k-reguläre Grafik und die Grafik selbst soll Grad habenk. Ebenso a Bipartitale Grafik in dem alle zwei Scheitelpunkte auf der gleichen Seite der zweizeiten wie einander den gleichen Grad haben, wird als a genannt Biregular Graph.
  • Eine ungerichtete, vernetzte Grafik hat eine Eulerianischer Weg Wenn und nur wenn es entweder 0 oder 2 Scheitelpunkte von ungerem Grad hat. Wenn es 0 Scheitelpunkte von ungerem Grad hat, ist der eulerische Pfad eine eulerische Schaltung.
  • Eine gerichtete Grafik ist a Regie geführt Pseudoforest wenn und nur wenn jeder Scheitelpunkt über den 1. A. Funktionsgrafik ist ein Sonderfall eines Pseudoforests, bei dem jeder Scheitelpunkt genau 1 im Freien hat.
  • Durch Brooks 'Theorem, jede Grafik G Anders als eine Clique oder ein seltsamer Zyklus hat Chromatische Zahl höchstens δ (G), und von Vizes -Theorem Jede Grafik hat Chromatischer Index höchstens δ (G)+1.
  • A k-Degeneriert Diagramm ist ein Diagramm, in dem jeder Untergraph höchstens einen Scheitelpunkt des Grades hat k.

Siehe auch

Anmerkungen

  1. ^ Diestel, S. 5, 28
  2. ^ Ciotti V (2015). "Abschluss Korrelationen in signierten sozialen Netzwerken". Physica A: Statistische Mechanik und ihre Anwendungen. 422: 25–39. Arxiv:1412.1024. Bibcode:2015phya..422 ... 25c. doi:10.1016/j.physa.2014.11.062. S2CID 4995458.
  3. ^ Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G (Januar 2021). "Topologische Auswirkungen negativer Verbindungen auf die Stabilität des Gehirnnetzwerks im Ruhezustand". Wissenschaftliche Berichte. 11 (1): 2176. Bibcode:2021natsr..11.2176s. doi:10.1038/s41598-021-81767-7. PMC 7838299. PMID 33500525.
  4. ^ Diestel S.216
  5. ^ Deza, Antoine; Levin, Asaf; Meesum, Syed M.; Onn, Shmuel (Januar 2018). "Optimierung über Gradsequenzen". Siam Journal über diskrete Mathematik. 32 (3): 2067–2079. Arxiv:1706.03951. doi:10.1137/17m1134482. ISSN 0895-4801. S2CID 52039639.

Verweise