Erősen reguláris gráf

A matematika, azon belül a gráfelmélet területén egy erősen reguláris gráf (strongly regular graph, srg) olyan reguláris gráf, amely néhány további követelménynek is megfelel. Ha G = (V,E) egy v csúccsal rendelkező k fokszámú reguláris gráf, akkor erősen reguláris, ha létezik olyan λ és μ egész szám, melyekre:

  • Bármely két szomszédos csúcsnak λ közös szomszédja van.
  • Bármely két nem szomszédos csúcsnak μ közös szomszédja van.
Gráfcsaládok automorfizmusukkal meghatározva
távolságtranzitívtávolságreguláriserősen reguláris
szimmetrikust-tranzitív, t ≥ 2ferdeszimmetrikus
(ha összefüggő)
csúcs- és éltranzitív
éltranzitív és reguláriséltranzitív
csúcstranzitívreguláris(ha páros)
bireguláris
Cayley-gráfzérószimmetrikusaszimmetrikus

Az erősen reguláris gráfokat néha paramétereikkel jelölik: srg(v, k, λ, μ) vagy egyszerűen (v, k, λ, μ), ha a kontextusból egyértelmű, hogy erősen reguláris gráfról van szó. Az erősen reguláris gráfokat Raj Chandra Bose vezette be 1963-ban.[1]

Egyes szerzők kizárják a definíciót triviálisan teljesítő gráfokat, tehát azokat, melyek azonos méretű teljes gráfok diszjunkt uniójaként állnak elő (μ=0),[2][3] illetve ezek komplementereit, a Turán-gráfokat.

Az srg(v, k, λ, μ) komplementere szintén erősen reguláris. Paraméterei: srg(v, v−k−1, v−2−2k+μ, v−2k+λ).

Minden erősen reguláris gráf 2 átmérőjű távolságreguláris gráf (az elfajult μ=0 esetet nem tekintve).

TulajdonságokSzerkesztés

A paraméterek közötti kapcsolatokSzerkesztés

Az srg(v, k, λ, μ) négy paramétere nem független egymástól, és eleget kell tenniük a következő összefüggésnek:

 ,

melyhez a következő, egyszerű leszámlálási okoskodással lehet eljutni:

  • Osszuk szét a gráf csúcsait három szintre a következőképpen: válasszunk ki egy tetszőleges csúcsot gyökérnek, ő lesz a 0. szinten. A gyökércsúcs k szomszédját helyezzük el az 1. szintre, az összes többi csúcs a 2. szinten lesz.
  • Az 1. szinten lévő csúcsok közvetlen kapcsolatban vannak a gyökérrel, ezért a gyökérrel λ közös szomszédjuk van, melyeknek szintén az 1. szinten kell lenniük. Mivel a csúcsok fokszáma k, ezért   él maradt meg minden 1. szintű csúcs számára ahhoz, hogy a 2. szinten lévő csúcsokhoz csatlakozzon. Ezért minden 1. szintű és a 2. szint között   él húzódik.
  • A 2. szinten lévő csúcsok nem közvetlenül csatlakoznak a gyökérhez, ezért μ közös szomszédjuk van a gyökérrel, melyeknek mind az 1. szinten kell lenniük. A 2. szinten   csúcs van, és mindegyik μ az 1. szinten lévő csúccsal van összekötve. Ezért az 1. és 2. szint közötti élek száma  .
  • Az 1. és 2. szintet összekötő élekre vonatkozó két kifejezést egyenlővé tesszük.

Szomszédsági mátrixSzerkesztés

Jelölje a v rendű egységmátrixot I, a minden elemében 1-eseket tartalmazó mátrixot pedig J. Egy erősen reguláris gráf A szomszédsági mátrixa két egyenlőségnek tesz eleget. Először is,

 

ami a csúcsok fokszámára vonatkozó követelmény triviális újrafogalmazása; mellesleg ez megmutatja, hogy k a szomszédsági mátrix sajátértéke, csak 1-esekből álló sajátvektorral. Másodszor,

 

ami az erős regularitási feltételt fejezi ki. Az első tag megadja a bármely csúcstól az összes többi csúcsba vezető két lépéses utak számát, a második tag az egy lépéses utakét, a harmadik tag pedig a nulla lépéses utakét. Az éllel összekötött csúcspárokra az egyenlőség arra egyszerűsödik, hogy az ilyen két lépéses utak száma éppen λ. A nem közvetlenül szomszédos csúcspároknál arra, hogy az ilyen két lépéses utak száma μ. A triviális saját magával párba állított csúcsra pedig arra, hogy a fokszám egyenlő k-val.

Megfordítva, az olyan gráfok, melyek nem teljes vagy nullgráfok, szomszédsági mátrixuk pedig a fenti két feltételt kielégíti, erősen regulárisak.[4]

SajátértékekSzerkesztés

  • A gráf szomszédsági mátrixának pontosan három sajátértéke van:
    • k, aminek multiplicitása 1 (ahogy fent látható)
    •  , aminek multiplicitása  
    •  , aminek multiplicitása  
  • Mivel a multiplicitásoknak egész számoknak kell lenniük, a fenti alakok további megszorításokat adnak v, k, μ és λ értékeire, ez az úgynevezett „Krein-feltétel”.
  • Az olyan erősen reguláris gráfokat, melyekre   konferenciagráfoknak nevezzük, a konferenciamátrixokkal való kapcsolatuk miatt. Paramétereik a következőre egyszerűsíthetők:
 
  • Az olyan erősen reguláris gráfok, melyekre  , sajátértékei egész számok, és multiplicitásaik nem egyenlőek.

PéldákSzerkesztés

 
A 13 rendű Paley-gráf, ami az srg(13,6,2,3) paraméterű erősen reguláris gráf.

Egy erősen reguláris gráfot primitívnek tekintünk, ha a gráf és komplementere is összefüggő. A fent felsorolt gráfok mind primitívek, egyébként fennállna, hogy μ=0 vagy μ=k.

Moore-gráfokSzerkesztés

A λ = 0 paraméterű erősen reguláris gráfok háromszögmentesek. A 3-nál kevesebb csúcsú teljes gráfokon és az összes teljes páros gráfon kívül csak a fenti listában szereplő hét gráf ismert közülük. A λ = 0 és μ = 1 paraméterű erősen reguláris gráfok 5 girthű Moore-gráfok. A fenti listában szereplő három ilyen gráf, (5, 2, 0, 1), (10, 3, 0, 1) és (50, 7, 0, 1) ismert ezek közül. Az egyetlen további lehetséges, Moore-gráfot előállító paraméterhalmaz a (3250, 57, 0, 1); nem ismert, hogy létezik-e ez a gráf, és ha igen, egyedi-e.

Kapcsolódó szócikkekSzerkesztés

FordításSzerkesztés

  • Ez a szócikk részben vagy egészben a Strongly regular graph című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

JegyzetekSzerkesztés

  1. https://projecteuclid.org/euclid.pjm/1103035734, R. C. Bose, Strongly regular graphs, partial geometries and partially balanced designs, Pacific J. Math 13 (1963) 389–419. (p. 122)
  2. Brouwer, Andries E; Haemers, Willem H. Spectra of Graphs. p. 101. [2012. március 16-i dátummal az eredetiből archiválva]. (Hozzáférés: 2014. október 10.)
  3. Godsil, Chris; Royle, Gordon. Algebraic Graph Theory. Springer-Verlag New York, 2001, p. 218.
  4. Cameron, P.J. & van Lint, J.H. (1991), Designs, Graphs, Codes and their Links, London Mathematical Society Student Texts 22, Cambridge University Press, p. 37, ISBN 978-0-521-42385-4
  5. Weisstein, Eric W.: Schläfli graph (angol nyelven). Wolfram MathWorld

IrodalomSzerkesztés

További információkSzerkesztés