Scheitelpunkt-verbundenes Diagramm

In der Graphentheorie wird ein verbundener Graph "als k - Scheitelpunkt verbunden bezeichnet, wenn er mindestens k + 1 Scheitelpunkte hat und wenn er nach dem Entfernen von k - 1 noch verbunden bleibt " .

Definitionen

Ein anderer Graph als ein vollständiger Graph hat den Scheitelpunkt- Verbindungsgrad k, wenn es sich um einen k -verbundenen Scheitelpunkt handelt, ohne k + 1 -verbundener Scheitelpunkt zu sein. Wenn also k die Größe der kleinsten Teilmenge von Scheitelpunkten ist, deren Löschung den Graphen trennt. Vollständige Diagramme sind in dieser Version der Definition nicht enthalten, da sie nicht durch Entfernen von Scheitelpunkten getrennt werden können. Der vollständige Graph mit n Eckpunkten hat den Grad der Verbundenheit n-1 .

Eine äquivalente Definition ist, dass ein Graph mit mindestens zwei Scheitelpunkten k -verbundener Scheitelpunkt ist, für jedes Paar seiner Scheitelpunkte gibt es k unabhängige Ketten, die diese Scheitelpunkte verbinden; das ist Mengers Satz . Diese Definition ergibt die gleiche Antwort n - 1 für die Konnektivität des vollständigen Graphen K n .

Ein mit 1 Scheitelpunkt verbundener Graph wird als verbundener Graph bezeichnet . Ein 2-Scheitelpunkt-verbundener Graph, der als zweifach verbundener Graph bezeichnet wird . Ein 3-verbundener Graph wird auch als Triconnected bezeichnet.

Ein regulärer Graph vom Grad k ist höchstens k -zusammenhängend-Vertex- und k - verbunden Kante . Wenn es sich tatsächlich um k -verbundene Oberseite und k -verbundene Kante handelt, wird es als optimal verbunden bezeichnet .

Beispiele

Für alle n ist der vollständige Graph K n (regulär vom Grad n - 1) optimal verbunden.
Für alle k > 2 und alle j > 1 ist der Fräsgraph Wd ( k , j ) 1-Scheitelpunkt-verbunden. Um es in j verbundene Komponenten zu trennen , reicht es aus, seinen Scheitelpunkt von höchstem Grad zu entfernen: seinen Mittelpunkt.
Der Zyklusgraph C n ist für alle n > 3 mit 2 Scheitelpunkten verbunden .
Der Iofinova-Ivanov 110-Graph ist mit 3 Scheitelpunkten verbunden.

Das Biggs-Smith-Diagramm ist 3-regulär, 3-Scheitelpunkt-verbunden und 3-Kanten-verbunden: Es ist optimal verbunden.
Der Mühlengraph Wd (5,4) ist nicht mehr verbunden, wenn wir seinen zentralen Scheitelpunkt entfernen: Er ist mit 1 Scheitelpunkt verbunden.
Der vollständige Graph K 6 ist mit 5 Scheitelpunkten verbunden.

Anzahl der Graphen entsprechend ihrer Vertex-Konnektivität

Anzahl der mit einfachen Scheitelpunkten verbundenen Graphen mit Scheitelpunkten für 1 bis 9 unter Bezugnahme auf OEIS : $k$ $nicht$ $nicht$

$k$ \. $nicht$	1	2	3	4	5	6	7	8	9	OEIS
gesamt	1	2	4	11	34	156	1044	12346	274668	A000088
1	1	1	2	6	21	112	853	11117	261080	A001349
2	0	1	1	3	10	56	468	7123	194066	A002218
3	0	0	1	1	3	17	136	2388	80890	A006290
4	0	0	0	1	1	4	25	384	14480	A086216
5	0	0	0	0	1	1	4	39	1051	A086217
6	0	0	0	0	0	1	1	5	59
7	0	0	0	0	0	0	1	1	5

Anzahl einfacher, genau mit dem Scheitelpunkt verbundener Diagramme mit Scheitelpunkten: $k$ $nicht$

$k$ \. $nicht$	1	2	3	4	5	6	7	8	9	OEIS
0	0	1	2	5	13	44	191	1229	13588
1	1	0	1	3	11	56	385	3994	67014	A052442
2	0	1	0	2	7	39	332	4735	113176	A052443
3	0	0	1	0	2	13	111	2004	66410	A052444
4	0	0	0	1	0	3	21	345	13429	A052445
5	0	0	0	0	1	0	3	34	992
6	0	0	0	0	0	1	0	4	54

Literaturverzeichnis

Jiří Matoušek und Jaroslav Nešetřil , Einführung in die diskrete Mathematik , Springer ,2004( online lesen )
Reinhard Diestel, Graphentheorie , Springer-Verlag, Slg. "Graduate Texts in Mathematics, Band 173",2016, 5 th ed. 447 p. ( ISBN 978-3-662-53621-6 und 978-3-96134-005-7 , online lesen )
Lutz Volkmann, Fundamente der Graphentheorie , Springer,1996( ISBN 3-211-82774-9 , online lesen ).
Alexander Schrijver , Kombinatorische Optimierung: Polyeder und Effizienz , Springer,20031881 (3 Bände) p. ( ISBN 978-3-540-44389-6 )

Externe Links

(en) Eric W. Weisstein , „ k-Connected Graph “ , auf MathWorld

In Verbindung stehender Artikel