Граф делителей нуля

График нуля делителей $\mathbb {Z} _{2}\times \mathbb {Z} _{4}$, единственный возможный граф делителей нуля, который является деревом , но не звездой

В математике , а точнее в комбинаторной коммутативной алгебре , граф делителей нуля — это неориентированный граф, представляющий делители нуля коммутативного кольца . он имеет элементы кольца , В качестве вершин — пары элементов, произведение которых равно нулю а в качестве ребер .

Определение

Существует два варианта обычно используемого графа делителей нуля.В исходном определении Бека (1988) вершины представляют все элементы кольца. В более позднем варианте, изученном Андерсоном и Ливингстоном (1999) , вершины представляют собой только делители нуля данного кольца.

Примеры

Если $n$ полупростое число (произведение двух простых чисел )то граф делителей нуля кольца целых чисел по модулю $n$ (вершинами которого являются только делители нуля) является либо полным графом , либо полным двудольным графом .Это полный график $K_{p-1}$ в случае, если $n=p^{2}$ для некоторого простого числа $p$. В этом случае все вершины являются ненулевыми кратными $p$, а произведение любых двух из этих чисел равно нулю по модулю $p^{2}$.

Это полный двудольный граф $K_{p-1,q-1}$ в случае, если $n=pq$ для двух различных простых чисел $p$ и $q$. Две стороны двудольного деления — это $p-1$ ненулевые кратные $q$ и $q-1$ ненулевые кратные $p$, соответственно. Два числа (которые сами по себе не равны нулю по модулю $n$) умножить на ноль по модулю $n$ тогда и только тогда, когда одно кратно $p$ а другой кратен $q$, поэтому в этом графе есть ребро между каждой парой вершин на противоположных сторонах двудольного деления и нет других ребер. В более общем смысле, граф делителей нуля — это полный двудольный граф для любого кольца, которое является произведением двух областей целостности .

Единственные графы циклов , которые можно реализовать как графы с нулевым произведением (с делителями нуля в качестве вершин), — это циклы длины 3 или 4. Единственные деревья , которые можно реализовать как графы с делителями нуля, — это звезды (полные двудольные графы, являющиеся деревьями) и дерево с пятью вершинами, сформированное как граф с делителями нуля. $\mathbb {Z} _{2}\times \mathbb {Z} _{4}$.

Характеристики

В версии графа, включающей все элементы, 0 является универсальной вершиной , а делители нуля можно идентифицировать как вершины, имеющие соседа, отличного от 0.Поскольку граф всех элементов кольца имеет универсальную вершину, он всегда связен и имеет диаметр не более двух. График всех делителей нуля непуст для любого кольца, не являющегося областью целостности . Он остается связным, имеет диаметр не более трех, и (если он содержит цикл ) имеет обхват не более четырех.

Граф делителей нуля кольца, не являющегося областью целостности, конечен тогда и только тогда, когда кольцо конечно . Более конкретно, если граф имеет максимальную степень $d$, кольцо имеет не более $(d^{2}-2d+2)^{2}$ элементы.Если кольцо и граф бесконечны, каждое ребро имеет конец с бесконечным числом соседей.

Бек (1988) предположил , что (как и идеальные графы ) графы с делителями нуля всегда имеют одинаковое кликовое число и хроматическое число . Однако это неправда; контрпример Андерсоном был открыт и Насиром (1993) .