Silně pravidelný graf
V teorii grafů je silně pravidelný graf graf, který má následující vlastnosti:
Dovolit být pravidelný graf s vrcholy a stupněm . Říká se, že je silně pravidelné , pokud existují celá čísla a taková, že:
![G=(V,E)](https://wikimedia.org/api/rest_v1/media/math/render/svg/644a8d85ee410b6159ca2bdb5dcb9097e2c8f182)
![proti](https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597)
![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
![\lambda](https://wikimedia.org/api/rest_v1/media/math/render/svg/b43d0ea3c9c025af1be9128e62a18fa74bedda2a)
![\mu](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fd47b2a39f7a7856952afec1f1db72c67af6161)
- Jakékoli dva nesousedící vrcholy mají společné sousedy.
![\mu](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fd47b2a39f7a7856952afec1f1db72c67af6161)
Grafy tohoto druhu se někdy označují jako .
![{\displaystyle srg(v,k,\lambda ,\mu )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ffcc692891f4966e1f6d6815f7645a87ed483dc)
Někteří autoři vylučují grafy splňující podmínky triviálně, konkrétně grafy, které jsou disjunktním spojením jednoho nebo více úplných grafů stejné velikosti [1] [2] , a jejich doplňky , Turanovy grafy .
Silně pravidelný graf je vzdálenostně pravidelný s průměrem , ale pouze pokud je nenulový.
![2](https://wikimedia.org/api/rest_v1/media/math/render/svg/901fc910c19990d0dbaaefe4726ceb1a4e217a0f)
![\mu](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fd47b2a39f7a7856952afec1f1db72c67af6161)
Vlastnosti
- Čtyři parametry v nejsou nezávislé a musí splňovat následující podmínku:
![{\displaystyle srg(v,k,\lambda ,\mu )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ffcc692891f4966e1f6d6815f7645a87ed483dc)
Tuto podmínku lze získat velmi jednoduše spočítáním argumentů takto:
- Představte si, že vrcholy grafu leží na třech úrovních. Zvolme libovolný vrchol jako kořen, úroveň . Potom jeho sousední vrcholy leží na úrovni a všechny zbývající vrcholy leží na úrovni .
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950)
![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
![jeden](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf)
![2](https://wikimedia.org/api/rest_v1/media/math/render/svg/901fc910c19990d0dbaaefe4726ceb1a4e217a0f)
- Vrcholy úrovně jsou spojeny přímo s kořenem, a proto musí mít další sousedy, kteří jsou sousedy kořene, a tito sousedé musí také ležet na úrovni . Protože každý vrchol má stupeň , existují hrany spojující každý vrchol úrovně s úrovní .
![jeden](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf)
![\lambda](https://wikimedia.org/api/rest_v1/media/math/render/svg/b43d0ea3c9c025af1be9128e62a18fa74bedda2a)
![jeden](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf)
![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
![{\displaystyle k-\lambda-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b52a4adfeda2784ea83a927f21096ff5a70ce2b)
![jeden](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf)
![2](https://wikimedia.org/api/rest_v1/media/math/render/svg/901fc910c19990d0dbaaefe4726ceb1a4e217a0f)
- Vrcholy úrovně nejsou přímo spojeny s kořenem, a proto musí mít společné sousedy s kořenem a všichni tito sousedé musí ležet na úrovni . To znamená, že vrcholy úrovně jsou připojeny ke každému vrcholu úrovně a každý z vrcholů úrovně 1 je připojen k vrcholům úrovně . Dostaneme, že počet vrcholů v úrovni je roven .
![2](https://wikimedia.org/api/rest_v1/media/math/render/svg/901fc910c19990d0dbaaefe4726ceb1a4e217a0f)
![\mu](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fd47b2a39f7a7856952afec1f1db72c67af6161)
![jeden](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf)
![\mu](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fd47b2a39f7a7856952afec1f1db72c67af6161)
![jeden](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf)
![2](https://wikimedia.org/api/rest_v1/media/math/render/svg/901fc910c19990d0dbaaefe4726ceb1a4e217a0f)
![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
![{\displaystyle k-\lambda-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7b52a4adfeda2784ea83a927f21096ff5a70ce2b)
![2](https://wikimedia.org/api/rest_v1/media/math/render/svg/901fc910c19990d0dbaaefe4726ceb1a4e217a0f)
![2](https://wikimedia.org/api/rest_v1/media/math/render/svg/901fc910c19990d0dbaaefe4726ceb1a4e217a0f)
![{\displaystyle k(k-\lambda -1)/\mu }](https://wikimedia.org/api/rest_v1/media/math/render/svg/728eef43ef4909e324dbc2784abb78b5a493cf66)
- Celkový počet vrcholů na všech třech úrovních je tedy stejný a po transformaci dostaneme .
![{\displaystyle v=1+k+k(k-\lambda -1)/\mu }](https://wikimedia.org/api/rest_v1/media/math/render/svg/5dd678e6fa28ad60aa80f32837d4e0566b5ccde3)
![{\displaystyle (vk-1)\mu =k(k-\lambda -1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f8c99bd2a24a9b4a667eb225d34e9aaac1a59160)
- Označme matici identity (řádu ) a nechť označme matici, jejíž všechny prvky jsou rovny . Matice sousedství silně regulárního grafu má následující vlastnosti:
![{\displaystyle \mathbf {I} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/8a458c8aeb096ce732abf346ae8edf3e4f53a126)
![proti](https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597)
![{\displaystyle \mathbf {J} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/7686846b1a6b756cb514954000004ab5e7b2a5ba)
![{\mathbf A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0795cc96c75d81520a120482662b90f024c9a1a1)
![{\displaystyle \mathbf {A} \mathbf {J} =k\mathbf {J} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/98715dce35195733ab50844810f901d33889c64c)
(Toto je triviální parafráze požadavku, aby se stupeň vrcholů rovnal ).![k](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40)
![{\displaystyle {\mathbf {A} }^{2}+(\mu -\lambda ){\mathbf {A} }+(\mu -k){\mathbf {I} }=\mu {\mathbf { J} }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a6f3c292ccbbe112508b736e2f85d7a2213fc454)
(První člen, , udává počet dvouskokových cest z libovolného vrcholu ke všem vrcholům. Druhý člen, , odpovídá přímo spojeným hranám. Třetí člen, , odpovídá triviálním párům, když jsou vrcholy v páru stejné ).![{\displaystyle {\mathbf {A} }^{2))](https://wikimedia.org/api/rest_v1/media/math/render/svg/548bd2b90e6b786ad7bd5d04f6981bdf295ac2cb)
![{\displaystyle (\mu -\lambda ){\mathbf {A} ))](https://wikimedia.org/api/rest_v1/media/math/render/svg/f90f4fff91097722e03a9242a150b8a5bc1973f7)
![{\displaystyle (\mu -k){\mathbf {I} }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/de77556a149f1e431b4ab3c4885a5bb5560f52c3)
- Graf má přesně tři vlastní čísla :
, jehož násobek se rovná 1
, jehož násobnost se rovná![{\displaystyle {\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bbc8e9b9ead0ab886e5b0a9b462a154538d4f273)
, jehož násobnost se rovná![{\displaystyle {\frac {1}{2}}\left[(v-1)+{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10c4e7c6833df4ca6e1613efb30a7f10d594d563)
- Silně regulární grafy, pro které se nazývají konferenční grafy kvůli jejich spojení se symetrickými konferenčními maticemi . Počet nezávislých parametrů těchto grafů je snížen na jeden - .
![{\displaystyle 2k+(v-1)(\lambda -\mu )=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f9c99b3989eb7b75f95d769382d5aa7f4177d524)
![{\displaystyle srg\left(v,{\frac {v-1}{2)),{\frac {v-5}{4)),{\frac {v-1}{4))\right) }](https://wikimedia.org/api/rest_v1/media/math/render/svg/3134626a34402c858c2c8901b1210ecd1bdc54ef)
- Silně pravidelné grafy, pro které mají vlastní čísla celá čísla s nestejnými násobnostmi.
![{\displaystyle 2k+(v-1)(\lambda -\mu )\neq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7280dcbf86087df8beab97fb69e55f9e06cefeb1)
- Přídavek je také silně pravidelný - je .
![{\displaystyle srg(v,k,\lambda ,\mu )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9ffcc692891f4966e1f6d6815f7645a87ed483dc)
![{\displaystyle srg(v,vk-1,v-2-2k+\mu ,v-2k+\lambda )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43778827990de79b49fea337f9f1c8c4294422f3)
Příklady
O silně regulárním grafu se říká , že je jednoduchý , pokud jsou graf i jeho doplněk propojeny. Všechny výše uvedené grafy jsou jednoduché, protože jinak nebo .
![\mu=0](https://wikimedia.org/api/rest_v1/media/math/render/svg/3753282c0ad2ea1e7d63f39425efd13c37da3169)
![{\displaystyle \mu=k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40391dd2c6a7358dfe6beba4ea503f06c05d2e09)
Counts of Moore
Silně pravidelné grafy s neobsahují trojúhelníky . Kromě úplných grafů s méně než 3 vrcholy a všech úplných bipartitních grafů je všech výše uvedených sedm známých grafů tohoto typu. Silně pravidelné grafy s a jsou Mooreovy grafy s obvodem 5. Opět platí, že tři výše uvedené grafy s parametry a jsou jediné známé grafy tohoto druhu. Jediná další možná sada parametrů odpovídající Moorovým grafům je . Není známo, zda takový graf existuje, a pokud ano, zda je jedinečný.
![{\displaystyle \lambda =0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/00c4bba30544017fe76932de5a4e25adb5512d95)
![\mu=1](https://wikimedia.org/api/rest_v1/media/math/render/svg/820c85551af65c6bedaf1b895fbd99bd9e23ec4f)
![{\displaystyle srg(5,2,0,1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/897e7e07d8923f4e6bf6cd564443254b0357b600)
![{\displaystyle srg(10,3,0,1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7448aa0cfe49f587c7c5f26a73b3601c165dedbd)
![{\displaystyle srg(50,7,0,1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/46bd00cc7bdcb5d11340f4374b23f9faceaf4b73)
![{\displaystyle srg(3250,57,0,1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ae37367b597903eec2e1dc938e99f72b2bdffe5)
Viz také
Poznámky
- ↑ Brouwer, 2012 , str. 101.
- ↑ Godsil, 2001 , str. 218.
- ↑ Weisstein, Eric W. Schläfli graf (anglicky) na webu Wolfram MathWorld .
Literatura
- Brouwer AE, Cohen AM, Neumaier A. Distance Regular Graphs . - Berlín, New York: Springer-Verlag, 1989. - ISBN 3-540-50619-5 .
- Brouwer A.E., Haemers W.H. Spectra of Graphs (anglicky) . - New York: Springer-Verlag, 2012. - Sv. 418.- (Universitex). — ISBN 978-1-4614-1938-9 .
- Godsil C., Royle G. Teorie algebraických grafů (anglicky) . - New York: Springer-Verlag, 2001. - ISBN 0-387-95241-1 .
Odkazy