Isetäienduv graaf: erinevus redaktsioonide vahel
Eemaldatud sisu Lisatud sisu
P r2.7.3) (Robot: lisatud en:Self-complementary graph |
korrigeeritud |
||
| 2. rida: | 2. rida: | ||
'''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]]. |
'''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]]. |
||
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äigraaf]]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äigraaf]]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. |
||
Redaktsioon: 11. detsember 2012, kell 12:44
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äigraafi 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.