Graf nulového dělitele - Zero-divisor graph

The graf nulového dělitele z ${ displaystyle mathbb {Z} _ {2} times mathbb {Z} _ {4}}$, jediný možný graf nulového dělitele, kterým je strom, ale ne hvězda

V matematice a konkrétněji v kombinatorická komutativní algebra, a graf nulového dělitele je neorientovaný graf zastupující nulové dělitele a komutativní prsten. Má prvky prstenu jako své vrcholy a dvojice prvků, jejichž součin je nulový hrany.^[1]

Definice

Obvykle se používají dvě varianty grafu nulového dělitele. V původní definici Beck (1988), vrcholy představují všechny prvky prstenu.^[2] V pozdější variantě studoval Anderson & Livingston (1999), vrcholy představují pouze nulové dělitele daného prstenu.^[3]

Příklady

Li ${ displaystyle n}$ je semiprime číslo (součin dvou prvočísla ) pak graf nulového dělitele prstence celých čísel modulo ${ displaystyle n}$ (pouze s nulovými děliteli jako jeho vrcholy) je buď a kompletní graf nebo a kompletní bipartitní graf.Je to kompletní graf ${ displaystyle K_ {p-1}}$ v případě, že ${ displaystyle n = p ^ {2}}$ pro nějaké prvočíslo ${ displaystyle p}$. V tomto případě jsou vrcholy všechny nenulové násobky ${ displaystyle p}$a součin všech dvou z těchto čísel je 0 modulo ${ displaystyle p ^ {2}}$.^[3]

Jedná se o kompletní bipartitní graf ${ displaystyle K_ {p-1, q-1}}$ v případě, že ${ displaystyle n = pq}$ pro dvě odlišná prvočísla ${ displaystyle p}$ a ${ displaystyle q}$. Dvě strany bipartice jsou: ${ displaystyle p-1}$ nenulové násobky ${ displaystyle q}$ a ${ displaystyle q-1}$ nenulové násobky ${ displaystyle p}$, resp. Dvě čísla (která sama nejsou nulová modulo) ${ displaystyle n}$) vynásobte na nulu modulo ${ displaystyle n}$ právě tehdy, pokud je jedna násobkem ${ displaystyle p}$ a druhá je násobkem ${ displaystyle q}$, takže tento graf má hranu mezi každou dvojicí vrcholů na opačných stranách bipartice a žádné další hrany. Obecněji je graf s nulovým dělitelem úplný bipartitní graf pro jakýkoli prsten, který je produkt ze dvou integrální domény.^[3]

Jediný cyklické grafy které lze realizovat jako grafy s nulovým součinem (s nulovými děliteli jako vrcholy) jsou cykly délky 3 nebo 4.^[3]Jediný stromy které lze realizovat jako grafy nulového dělitele hvězdy (kompletní bipartitní grafy, které jsou stromy) a pětvertexový strom vytvořený jako graf nulového dělitele ${ displaystyle mathbb {Z} _ {2} times mathbb {Z} _ {4}}$.^[1][3]

Vlastnosti

Ve verzi grafu, který obsahuje všechny prvky, je 0 a univerzální vrchol a nulové dělitele lze identifikovat jako vrcholy, které mají souseda jiného než 0. Protože má univerzální vrchol, je graf všech kruhových prvků vždy spojen a má průměr nejvýše dva. Graf všech nulových dělitelů je neprázdný pro každý prsten, který není integrální doména. Zůstává připojený, má průměr maximálně tři,^[3] a (pokud obsahuje cyklus) má obvod maximálně čtyři.^[4][5]

Graf nulového dělitele prstence, který není integrální doménou, je konečný právě tehdy, je-li prsten konečný.^[3] Přesněji řečeno, pokud má graf maximální stupeň ${ displaystyle d}$, prsten má nanejvýš ${ displaystyle (d ^ {2} -2d + 2) ^ {2}}$ Pokud jsou kruh a graf nekonečné, každá hrana má koncový bod s nekonečně mnoha sousedy.^[1]

Beck (1988) domníval se, že (jako perfektní grafy ) grafy s nulovým dělitelem mají vždy stejnou hodnotu číslo kliky a chromatické číslo. To však není pravda; protipříklad byl objeven uživatelem Anderson & Naseer (1993).^[6]

Reference