Протограф

Протограф — обобщение графа, который задается множеством элементов Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \{p_i,i\}=1,n} и матрицей соседства (смежности) Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle Mn*n} , состоящей из 0 и 1, где 1 означает соседство (смежность) элемента a элементу b.

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

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

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

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

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

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

Для задачи раскраски карты будем считать, что если элементы протографа на изображении соприкасаются только в одной точке, то соотношения смежности нет. Тогда можно перейти от карты Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle G1} к графу Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle G2} , тогда задача раскраски карты сводится к раскраске вершин графа Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle G2} .

Файл:Пример раскраски карты путем перехода от протографа G1 к графу G2 и раскраски его вершин.png

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

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

Ссылки

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