Протограф

Протограф — обобщение графа, который задается множеством элементов $\{p_{i},i\}=1,n$ и матрицей соседства (смежности) $Mn*n$, состоящей из 0 и 1, где 1 означает соседство (смежность) элемента a элементу b.

Примеры протографов

Стек и очередь являются характерными примерами протографов, так как при хранении этих структур в памяти ЭВМ не создается дополнительных сущностей для хранения их смежности (ребер), каждый элемент стека/очереди содержит указатель на следующий элемент (в случае использования динамической памяти) либо непосредственно соседствует в силу размещения в соседних адресах памяти (при использовании массива или реализация стека процессором, когда элементы стека последовательно хранятся в памяти ЭВМ начиная с адреса, который хранится в регистре SS – указателе сегмента стека, регистр SP указывает вершину стека).

Пример протографа стек

Пример протографа очередь

Раскраска протографа

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

Для задачи раскраски карты будем считать, что если элементы протографа на изображении соприкасаются только в одной точке, то соотношения смежности нет. Тогда можно перейти от карты $G1$ к графу $G2$, тогда задача раскраски карты сводится к раскраске вершин графа $G2$.

Пример раскраски карты путем перехода от протографа G1 к графу G2 и раскраски его вершин

Из утверждения о соответствии протографу графа следует, что любой протограф может быть раскрашен. Как следствие, для каждого протографа может быть указано его хроматическое число.

Ссылки

• Кручинин Сергей Владимирович Протографы и архиграфы как обобщение графов // Научно-исследовательские публикации. — 2017. — № 3 (41).