|
Можно ли нарисовать графы, изображенные на рисунках, не отрывая карандаша от бумаги? 
Подобные задачи достаточно часто встречаются в книжках по занимательной математике для младших школьников.
Решение.
Для того чтобы нарисовать любой граф не отрывая руки °т бумаги, необходимо в каждую вершину графа, за исключением начальной и конечной, войти столько же раз, сколько и выйти. Поэтому степени всех вершин нарисованного графа, кроме начальной и конечной, должны быть четными - такой граф должен иметь не более двух нечетных вершин!
Ясно, что левая фигура и конверт могут быть нарисованы не отрывая руки от бумаги, при этом рисунок должен начинаться в любой нечетной вершине: у первой фигуры две такие точки лежат на концах горизонтального отрезка, а у конверта такими двумя точками являются нижние углы конверта. Эмблема «Мерседеса» нарисована быть не может. Впервые графы, обладающие подобными свойствами, были исследованы великим русским математиком Леонардом Эйлером в 1736 году в связи со знаменитой задачей о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются эйлеровыми. Леонард Эйлер, совершая прогулку по городу, в котором он жил, — Кенигсбергу (ныне Калининград), поставил для себя задачу: прогуляться по всем мостам, перекинутым на два острова реки и между островами так, чтобы по каждому мосту пройти не более одного раза. Представим схему задачи Эйлера:  Ясно, что задача Эйлера при переводе на язык графов имеет 4 нечетных вершины и, следовательно, не решается.
|
