Приложение теории графов в различных областях науки и техники

Применение теории графов в школьном курсе математики

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

Условно их можно классифицировать, подразделив на несколько групп:

ь Задачи о мостах.

ь Логические задачи ь Задачи о «правильном» раскрашивании карт ь Задачи на построение уникурсальных графов Рассмотрим несколько типичных примеров решения задач каждого вида.

Одной из наиболее известных задач о мостах является эйлерова задача; все остальные сформулированы похожим образом и решаются по тому же принципу. Поэтому в данном параграфе мы не будем подробно останавливаться разборе этого типа задач.

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

Задача 1. Из трех человек, стоящих рядом, один всегда говорит правду (правдолюб), другой всегда лжет (лжец), а третий, смотря по обстоятельствам, говорит либо правду, либо ложь (дипломат). У стоящего слева спросили: «Кто стоит рядом с тобой?». Он ответил: «Правдолюб». Стоящему в центре задали вопрос: «Кто ты?», и он ответил: «Я дипломат». Когда у стоящего справа спросили: «Кто стоит рядом с тобой?», он сказал: «Лжец». Кто где стоял?

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

Рассмотрим первую возможность. Если «правдолюб» стоит слева, то рядом с ним, судя по его ответу, также стоит «правдолюб». У нас же стоит «лжец». Следовательно, эта расстановка не удовлетворяет условию задачи. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что позиция «дипломат», «лжец», «правдолюб» удовлетворяет задаче. Действительно, если «правдолюб» стоит справа, то, по его ответу, рядом с ним стоит «лжец», что выполняется. Стоящий в центре заявляет, что он «дипломат», и, следовательно, лжет (что возможно из условия), а стоящий справа также лжет. Таким образом, все условия задачи выполнены.

Задача 2. В обеденный перерыв члены строительной бригады разговорились о том, кто сколько газет читает. Выяснилось, что каждый выписывает и читает две и только две газеты, каждую газету читает пять человек, и любая комбинация читается одним человеком. Сколько различных газет выписывают члены бригады? Сколько человек в бригаде?

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

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

Любая географическая карта является многоугольным графом, в котором страны будут гранями, границы — ребрами, а окружающий страны Мировой океан — бесконечной гранью.

Для лучшего зрительного восприятия необходимо, чтобы страны с общей границей были раскрашены в разные цвета. Такую карту называют «правильно» раскрашенной.

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

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