Протограф (Математика)
Протограф — это обобщение графа, который задается множеством элементов  и матрицей соседства (смежности) , состоящей из 0 и 1, где 1 означает соседство (смежность) элемента a элементу b.

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

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

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

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

Ссылки 

 

Графы
