matematikai fogalom a gráfelméletben From Wikipedia, the free encyclopedia
A matematika, azon belül a gráfelmélet területén egy távolságreguláris gráf (distance-regular graph) olyan reguláris gráf, melyben bármely két v és w csúcsot kiválasztva, a v-től j távolságra és a w-től k távolságra lévő csúcsok száma kizárólag j, k, illetve i = d(v, w), azaz a két csúcs távolságának a függvénye.
Minden távolságtranzitív gráf távolságreguláris. És valóban, a távolságreguláris gráfokat a távolságtranzitív gráfok kombinatorikai általánosításaiként vezették be; számszerűen ugyanazok a regularitási paramétereik, de a távolságreguláris gráfok nem feltétlenül rendelkeznek nagy automorfizmus-csoporttal.
Egy átmérőjű gráf pontosan akkor távolságreguláris, ha minden -beli, egymástól távolságra lévő csúcspár esetén létezik olyan, egész számokból álló tömb, amire igaz, hogy bármely értékre megadja azon szomszédainak számát, melyek -től távolságra vannak, pedig megadja azon szomszédainak számát, melyek -től távolságra vannak. A távolságreguláris gráfot jellemző, egész számokból álló tömböt a gráf metszési tömbjének (intersection array) nevezik.
Két összefüggő távolságreguláris gráf pontosan akkor kospektrális, ha metszési tömbjeik megegyeznek.
Egy távolságreguláris gráf pontosan akkor nem összefüggő, ha kospektrális távolságreguláris gráfok diszjunkt uniójából áll.
Legyen egy távolságreguláris gráf, melynek metszési tömbje . Minden -re jelölje azt a -reguláris gráfot, melynek szomszédsági mátrixa, előáll a -ben távolságra lévő csúcspárok összekapcsolásával, és jelölje azon szomszédainak számát, melyek -től távolságra vannak, minden olyan -beli csúcspárra, melyek egymástól távolságra vannak.
Létezik olyan, a metszési mátrixának (intersection matrix) nevezett tridiagonális mátrix, hogy bármely -beli csúcsra:
,
ahol .
karakterisztikus polinomja megegyezik az minimálpolinomjával.
Néhány távolságreguláris gráf, illetve gráfcsalád:
Bármely for all értékre csak véges számú összefüggő, fokszámú távolságreguláris gráf létezik.[1]
A 3-reguláris távolságreguláris gráfok osztályozása már teljes.
A 13 különböző gráf a következő: a K4 (avagy tetraéder), a K3,3, a Petersen-gráf, a kocka, a Heawood-gráf, a Papposz-gráf, a Coxeter-gráf, a Tutte–Coxeter-gráf, a dodekaéder, a Desargues-gráf, a Tutte 12-cage, a Biggs–Smith-gráf és a Foster-gráf.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.