График с делителем нуля

редактировать

Z 2 × Z 4 {\ displaystyle \ mathbb {Z} _ {2} \ times \ mathbb {Z} _ {4}}

{\ displaystyle \ mathbb {Z} _ {2} \ times \ mathbb {Z} _ {4}}

, единственно возможное граф делителей нуля, который является деревом, но не звездой

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

Содержание

1 Определение
2 Примеры
3 Свойства
4 Ссылки

Определение

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

Примеры

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

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

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

Свойства

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

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

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

Ссылки