Turán-graf
Turán-graf
|
Turans graf (13.4)
|
|
Vurdering
|
T(ikke,r){\ displaystyle T (n, r)}
|
---|
Antall hjørner
|
ikke{\ displaystyle n}
|
---|
Antall kanter
|
~(r-1)ikke22r{\ displaystyle {\ frac {(r-1) n ^ {2}} {2r}}}
|
---|
Stråle
|
{∞r=12r≤ikke/21ellers{\ displaystyle \ left \ {{\ begin {array} {ll} \ infty & r = 1 \\ 2 & r \ leq n / 2 \\ 1 & {\ text {ellers}} \ end {array}} \ Ikke sant.}
|
---|
Diameter
|
{∞r=11r=ikke2Hvis ikke{\ displaystyle \ left \ {{\ begin {array} {ll} \ infty & r = 1 \\ 1 & r = n \\ 2 & {\ text {ellers}} \ end {array}} \ right.}
|
---|
Mesh
|
{∞r=1∨(ikke≤3∧r≤2)4r=23Hvis ikke{\ displaystyle \ left \ {{\ begin {array} {ll} \ infty & r = 1 \ vee (n \ leq 3 \ wedge r \ leq 2) \\ 4 & r = 2 \\ 3 & {\ text {ellers}} \ end {array}} \ høyre.}
|
---|
Kromatisk nummer
|
r{\ displaystyle r}
|
---|
I grafteori er en Turán-graf (bemerket ), også kalt en maksimalt mettet graf , et element i en familie av grafer som bærer navnet Pál Turán .
T(ikke,r){\ displaystyle T (n, r)}
Grafen har hjørner, delt inn i de mest balanserte mulige delmengdene, og hvert toppunkt er koblet til alle hjørnene som ikke er i delmengden. Med balansert mener vi at grafen har størrelsesundersett og størrelsesundersett .
T(ikke,r){\ displaystyle T (n, r)}ikke{\ displaystyle n}r{\ displaystyle r}(ikke mod r){\ displaystyle (n {\ text {mod}} r)}⌈ikke/r⌉{\ displaystyle \ lceil n / r \ rceil}r-(ikke mod r){\ displaystyle r- (n {\ text {mod}} r)}⌊ikke/r⌋{\ displaystyle \ lfloor n / r \ rfloor}
Definisjon
Turan-grafen over parametrene n og r, betegnet, har hjørner, delt inn i de mest balanserte mulige delmengdene, og hvert toppunkt er koblet til alle hjørnene som ikke er i delmengden. Med balansert mener vi at grafen vil ha størrelsesundersett og størrelsesundersett .
T(ikke,r){\ displaystyle T (n, r)}ikke{\ displaystyle n}r{\ displaystyle r}(ikke mod r){\ displaystyle (n {\ text {mod}} r)}⌈ikke/r⌉{\ displaystyle \ lceil n / r \ rceil}r-(ikke mod r){\ displaystyle r- (n {\ text {mod}} r)}⌊ikke/r⌋{\ displaystyle \ lfloor n / r \ rfloor}
Eiendommer
Den kromatiske antall av grafen er r .
T(ikke,r){\ displaystyle T (n, r)}
Spesielle tilfeller og inneslutninger
De komplette todelte grafene er grafer Turán.
De er cographs , det vil si at de kan dannes av usammenhengende fagforeninger og passasjer til den komplementære grafen . Vi kan gjøre det på følgende måte: For hver stall i den endelige grafen må du først lage en forening av alle toppunktene, gå til det komplementære (i hvert sett) for å ha klikker, deretter lage foreningen av alle klikker og gå igjen til det komplementære.
Historie
Turán-grafer er oppkalt etter Pál Turán , som definerte dem og brukte dem til bevis for Turans teorem .
Merknader og referanser
-
Chong-Yun Chao og George A Novacky Jr , “ On maximally saturated charts ”, Discrete Mathematics , Elsevier, vol. 41, n o to
1982, s. 139-143
-
Paul Turán , “ On an extremal problem in graph theory ”, Matematikai és Fizikai Lapok , vol. 48,1941, s. 436-452
Se også
Relatert artikkel
Ekstern lenke