Связанный граф

В теории графов связанный граф показывает, какие пары элементов некоторого частично упорядоченного множества имеют верхнюю границу . Строго говоря, любой граф G если существует частичный порядок ≤ в G со является связанным графом , свойством, что для любых вершин и v из G uv u является ребром G тогда вершинах и только тогда, когда u ≠ v и существует вершина w такая, что u ≤ w и v ≤ w .

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

Связанные графы иногда называют графами с верхней границей , но аналогично определенные графы с нижней границей составляют точно тот же класс - любая нижняя граница для ≤ легко увидеть как верхняя граница для двойственного частичного порядка ≥.

Ссылки

• МакМоррис, Франция; Заславский, Т. (1982). «Связанные графы частично упорядоченного множества». Журнал комбинаторики, информации и системных наук . 7 : 134–138.

• Лундгрен-младший; Мэйби, Дж. С. (1983). «Характеристика графов верхней границы». Конгресс Нумерантиум . 40 : 189–193.

• Бергстранд, диджей; Джонс, К.Ф. (1988). «О верхних границах графов частично упорядоченных множеств». Конгресс Нумерантиум . 66 : 185–193.

• Таненбаум, П.Дж. (2000). «Полисемия связанного графа» (PDF) . Электронный журнал комбинаторики . 7 : #R43. дои : 10.37236/1521 .