Kaksisuuntainen kaavio

In graafiteoria , eli biregular kaavio on kaksiosainen kaavio , jossa kaikki kärkipisteet molempien osien kuvaaja on sama aste . Merkitään ja kaksi osaa biregular kuvaajan. Jos aste kärkipisteet on ja aste kärkien on , kuvaajan sanotaan olevan -bike. $U$ $V$ $U$ $x$ $V$ $y$ $(x, y)$

Esimerkkejä

Täydelliset kahdenväliset kaaviot

Mikä tahansa täydellinen kahdenvälinen kaavio ( kuva ) on -biregular. ${\ displaystyle K_ {a, b}}$ $(a, b)$

Rombisen dodekaederin kaavio

Rombisen dodekaederin kaavio ( kuvio ) on -biregular. Itse asiassa sen kärjet on jaettu kahteen sarjaan: ${\ displaystyle (3,4)}$

joukko pisteiden asteen 4; $U$
joukko pisteiden asteen 3. $V$

Mitään 4 asteen kärkeä ei ole yhdistetty reunalla toiseen asteen 4 kärkeen; yhtään asteen 3 kärkeä ei ole yhdistetty reunalla toiseen asteen 3 kärkeen: tämä kaavio on todellakin kaksiosainen.

Pisteiden lukumäärä

Kaksisäännöllinen kaavio osista ja varmistaa tasa-arvon . $U$ $V$ ${\ displaystyle deg (U) \ cdot | U | = deg (V) \ cdot | V |}$

Esimerkiksi rombisessa dodekaedrissa meillä on 6 4-asteen kärkeä ja 8 3-asteen huippua, se tarkistaa hyvin . ${\ displaystyle 6 \ kertaa 4 = 8 \ kertaa 3}$

Voimme todistaa tämän tasa-arvon laskemalla kaksinkertaisesti :

päättyvien reunojen päiden lukumäärä on ; $U$ ${\ displaystyle deg (U) \ cdot | U |}$
päättyvien reunojen päiden lukumäärä on ; $V$ ${\ displaystyle deg (V) \ cdot | V |}$
jokaisella reunalla on yksi pää ja vain yksi sisään ja yksi pää ja vain yksi sisään , joten nämä kaksi numeroa ovat yhtä suuret. $U$ $V$

Muut ominaisuudet

Kaavio - säännöllinen kaksipuolinen on -birégulier. $ei$ ${\ displaystyle (n, n)}$
Reuna-transitiivisia kuvaaja (lukuun ottamatta kaaviot eristetty kärkipisteen), joka ei ole myös piste-transitiivinen on bi - säännöllinen.
Erityisesti ylitransitiivinen kaavio on joko säännöllinen tai kaksisuuntainen.
Levi kuvaajat on geometrinen kokoonpanot ovat biregular.
Kaksirivinen kaavio on geometrisen (abstraktin) kokoonpanon Levin kaavio vain ja vain, jos sen verkko on vähintään kuusi.

Huomautuksia ja viitteitä

(in) Edward R. Scheinerman Daniel H. Ullman , Fractional graafiteoria , New York, John Wiley & Sons Inc.,1997( ISBN 0-471-17864-0 , Math Reviews 1481157 ) , s. 137.
(en) Josef Lauri ja Raffaele Scapellato , graafisen automorfismin ja jälleenrakennuksen aiheita , Cambridge University Press ,2003, 20–21 Sivumäärä ( ISBN 978-0-521-52903-7 , lue verkossa ).
(sisään) Tamás Réti , " Zagrebin ensimmäisistä ja toisista vihjeistä " , MATCH Commun. Matematiikka. Laske. Chem. , voi. 68,2012, s. 169–188 ( lue verkossa ).
(in) Harald Gropp , Charles J. Colbourn ( ohj. ) Ja Jeffrey H. Dinitz ( toim. ), Handbook of kombinatorisista malleja , Chapman & Hall / CRC, Boca Raton, FL,2007, 2. painos , 353–355 Sivumäärä ( ISBN 9781584885061 ) , "VI.7-kokoonpanot".

Lähde

(fr) Tämä artikkeli on osittain tai kokonaan otettu Wikipedian englanninkielisestä artikkelista " Biregular graph " ( katso kirjoittajaluettelo ) .