График делителей нуля - Zero-divisor graph

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

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

Определение

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

Примеры

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

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

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

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

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

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

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

Рекомендации