Шаблон:К удалениюПротограф — это обобщение графа, который задается множеством элементов <math>\{p_i,i\}=1,n</math> и матрицей соседства (смежности) <math>Mn*n</math>, состоящей из 0 и 1, где 1 означает соседство (смежность) элемента a элементу b.
Примеры протографов
Стек и очередь являются характерными примерами протографов, так как при хранении этих структур в памяти ЭВМ не создается дополнительных сущностей для хранения их смежности (ребер), каждый элемент стека/очереди содержит указатель на следующий элемент (в случае использования динамической памяти) либо непосредственно соседствует в силу размещения в соседних адресах памяти (при использовании массива или реализация стека процессором, когда элементы стека последовательно хранятся в памяти ЭВМ начиная с адреса, который хранится в регистре SS – указателе сегмента стека, регистр SP указывает вершину стека).
Известной задачей является задача раскраски карты. Карта (если значащей информацией является смежность областей, а не площадь и форма границ) является протографом. При этом важно определиться, каким образом изображать такой протограф, а именно, являются ли смежными элементы, которые при графическом изображении имеют общую границу или общую соприкасаются в точке.
Для задачи раскраски карты будем считать, что если элементы протографа на изображении соприкасаются только в одной точке, то соотношения смежности нет. Тогда можно перейти от карты <math>G1</math> к графу <math>G2</math>, тогда задача раскраски карты сводится к раскраске вершин графа <math>G2</math>.
Из утверждения о соответствии протографу графа следует, что любой протограф может быть раскрашен. Как следствие, для каждого протографа может быть указано его хроматическое число.
