Isetäienduv graaf: erinevus redaktsioonide vahel
Eemaldatud sisu Lisatud sisu
PResümee puudub |
P →top: pisitoimetamine |
||
| 1. rida: | 1. rida: | ||
[[ |
[[Pilt:Self-complementary NZ graph.svg|pisi|Isetäinduv graaf (sinine) on isomorfne oma täiendiga (punane)]] |
||
'''Isetäienduv graaf''' on [[graaf]] mis on [[isomorfism|isomorfne]] tema [[graafi täiend |
'''Isetäienduv graaf''' on [[graaf]] mis on [[isomorfism|isomorfne]] tema [[graafi täiend|täiendiga]]. Üks lihtsaimad mittetriviaalsed isetäienduvad on ka 5-tipuline [[Graafi klikk ja vöö|5-vöö-regulaarne graaf]]. |
||
Ühe isetäienduvate graafide klassi moodustavad [[graafi sümmeetria|bisümmeetrilised]] Paley graafid. Iga [[Paley graaf]] on [[Graafi regulaarsus|tugevregulaarne]]. Kõik tugevregulaarsed, vähem kui 37 tipuga graafid on Paley graafid. |
Ühe isetäienduvate graafide klassi moodustavad [[graafi sümmeetria|bisümmeetrilised]] Paley graafid. Iga [[Paley graaf]] on [[Graafi regulaarsus|tugevregulaarne]]. Kõik tugevregulaarsed, vähem kui 37 tipuga graafid on Paley graafid. |
||
Iga ''n''-tipulise isetäienduva graafi servade arv on parajasti pool vastava [[täisgraaf]]i servade arvust, st ''n''(''n'' − 1)/4 serva, ja (kui servade arv on suurem kui 1) peab selle diameeter olema 2 või 3. Seega ''n''(''n'' −1) peab jaguma 4-ga, ''n'' peab olema kongruentne väärtustega 0 või 1 mod 4, mis tähendab et näiteks 6-tipuline graaf ei saa olla isetäienduv. |
Iga ''n''-tipulise isetäienduva graafi servade arv on parajasti pool vastava [[täisgraaf]]i servade arvust, st ''n''(''n'' − 1)/4 serva, ja (kui servade arv on suurem kui 1) peab selle diameeter olema 2 või 3. Seega ''n''(''n'' −1) peab jaguma 4-ga, ''n'' peab olema kongruentne väärtustega 0 või 1 mod 4, mis tähendab et näiteks 6-tipuline graaf ei saa olla isetäienduv. |
||
[[Kategooria:Graafiteooria]] |
[[Kategooria:Graafiteooria]] |
||
Viimane redaktsioon: 7. mai 2019, kell 15:06
Isetäienduv graaf on graaf mis on isomorfne tema täiendiga. Üks lihtsaimad mittetriviaalsed isetäienduvad on ka 5-tipuline 5-vöö-regulaarne graaf.
Ühe isetäienduvate graafide klassi moodustavad bisümmeetrilised Paley graafid. Iga Paley graaf on tugevregulaarne. Kõik tugevregulaarsed, vähem kui 37 tipuga graafid on Paley graafid.
Iga n-tipulise isetäienduva graafi servade arv on parajasti pool vastava täisgraafi servade arvust, st n(n − 1)/4 serva, ja (kui servade arv on suurem kui 1) peab selle diameeter olema 2 või 3. Seega n(n −1) peab jaguma 4-ga, n peab olema kongruentne väärtustega 0 või 1 mod 4, mis tähendab et näiteks 6-tipuline graaf ei saa olla isetäienduv.