Täydellinen kaksiosainen kaavio

Täydellinen kaksiosainen graafi ( biklik ) on erityinen kaksiosainen graafi , jossa mikä tahansa ensimmäisen osan kärki on yhdistetty pisteiden toisen osan kaikkiin pisteisiin.

Määritelmä

Täydellinen kaksiosainen graafi on kaksiosainen graafi siten, että minkä tahansa kahden kärjen ja , on reuna in . Täydellinen kaksiosainen graafi, jossa on osia kokoa ja on merkitty . $G:=(V_{1}+V_{2},E)$ $v_{1}\in V_{1}$ $v_{2}\in V_{2}$ $(v_{1}, v_{2})$ $G$ $|V_{1}|=m$ $|V_{2}|=n$ $K_{{m,n}}$

Esimerkkejä

Kaavioita kutsutaan tähdiksi , kaikki täydelliset kaksiosaiset kaaviot, jotka ovat puita , ovat tähtiä. $K_{{1,k}}$
Kuvaajaa kutsutaan kynsiksi ja sitä käytetään kuvaajien määrittelemiseen ilman kynsiä . $K_{{1,3}}$
Kaaviota kutsutaan joskus "yhteisgraafiksi", nimi juontaa juurensa klassiseen " talot ja kaivot " -ongelmaan, nykyaikaisessa tulkinnassa käyttäen "yhteisöllistä" formulaatiota (kytke kolme taloa veteen, sähköön ja kaasuun ylittämättä viivoja lentokone); ongelmaa ei voi ratkaista graafin epätasaisuuden vuoksi . $K_{{3,3}}$ $K_{{3,3}}$

Ominaisuudet

Ongelma löytää tietylle kaksiosaiselle graafille täydellinen kaksiosainen osagraafi tietyllä parametrilla on NP-täydellinen . $K_{{n,n}}$ $n$
Tasograafi ei voi sisältää graafia sivuarvona . Ulompi tasograafi ei voi sisältää sivuarvona (Tämä ei ole riittävä ehto tasomaisuudelle ja ulommalle tasolle, mutta välttämätön). Sitä vastoin mikä tahansa ei-tasograafi sisältää joko tai täydellisen graafin sivuaineena ( Pontryagin-Kuratovsky -lause ). $K_{{3,3}}$ $K_{{3,2}}$ $K_{{3,3}}$ $K_{5}$
Täydelliset kaksiosaiset graafit ovat Mooren graafit ja -solut . $K_{{n,n}}$ $(n,4)$
Täydelliset kaksiosaiset graafit ovat Turan - graafit . $K_{{n,n}}$ $K_{{n,n+1}}$
Täydellisellä kaksiosaisella graafilla on kärjen peitteen koko ja reunapeitekoko . $K_{{m,n}}$ $\min(m,n)$ $\max(m,n)$
Täydellisellä kaksiosaisella graafilla on enimmäiskoko riippumaton joukko . $K_{{m,n}}$ $\max(m,n)$
Täydellisen kaksiosaisen graafin vierekkäisyysmatriisissa on ominaisarvot ja kertoimilla , ja vastaavasti . $K_{{m,n}}$ ${\sqrt{nm))$ $-{\sqrt{nm))$ $0$ $yksi$ $yksi$ $n+m-2$
Täydellisen kaksiosaisen graafin Laplace-matriisissa on ominaisarvot , , , kertoimilla , ja vastaavasti . $K_{{m,n}}$ $n+m$ $n$ $m$ $0$ $yksi$ $m-1$ $n-1$ $yksi$
Täydellisessä kaksiosaisessa graafissa on virittäviä puita . $K_{{m,n}}$ $m^{{n-1}}\cdot n^{{m-1}}$
Täydellisen kaksiosaisen kaavion koko vastaa enimmäiskokoa . $K_{{m,n}}$ $\min(m,n)$
Täydellisellä kaksiosaisella graafilla on sopiva reunaväri , joka vastaa latinalaista neliötä . $K_{{n,n}}$ $n$

Kaksi viimeistä tulosta ovat seurausta Hallin lauseesta , jota sovelletaan -säännölliseen kaksiosaiseen graafiin. $k$

Katso myös

Kirjallisuus

John Adrian Bondy, USR Murty. Graafiteoria sovellusten kanssa. - Pohjois-Hollanti, 1976. - s. 5 . — ISBN 0-444-19451-7 . Arkistoitu alkuperäisestä 13. huhtikuuta 2010.
Reinhard Diestel. Graafiteoria // 3. - Springer , 2005. - S. 17 . — ISBN 3-540-26182-6 .