\ListokName{17. Плоские графы}

\shapkaUstnoA

\vspace{-.4cm}

\begin{wrapfigure}[9]{r}{.24\textwidth}\vspace{-.4cm}
    \includegraphics[width=\linewidth]{Listki/figs/t9.png}
\end{wrapfigure}


\zp Вовочка вырезал из  волейбольной сетки кусок  (см. рисунок) и, когда на него начали ругаться, заявил, что это материал для занятий теорией графов: узлы  сетки --- это вершины, а соединяющие их верёвочки --- рёбра. Чтобы продемонстрировать свои знания, Вовочка заявил, что в этом графе рёбер на 45 больше, чем вершин.  Не ошибается ли Вовочка?
%\lett Какое наименьшее число верёвочек надо разрезать Вовочке, чтобы сетка распалась на несколько частей?

\zp Справа нарисован план квартиры мечты Наталии Павловны. Она состоит из квадратных комнат, между каждыми двумя соседними из которых есть запертая дверь. Какое наименьшее число дверей нужно открыть, чтобы кот, отдыхающий в одной из комнат, мог гулять по всей квартире?

\z Ниже изображены правильные многогранники. Но, с другой стороны, это графы.
\lett Нарисуйте эти графы на плоскости так, чтобы их рёбра не пересекались.
\lett Посчитайте для каждого из них число вершин, рёбер и граней и вычислите  \textbf{В}-\textbf{Р}$+$\textbf{Г}.
\begin{center}\vspace{-.2cm}
    \includegraphics[width=.56\textwidth]{Listki/figs/platonovi_tela.jpg}
\vspace{-.2cm}
\end{center}

\textit{Плоским графом} будем называть нарисованный на  плоскости граф, рёбра не пересекаются.

\textit{Гранями} плоского графа называются куски, на которые его рёбра разбивают плоскость, Например, у плоского графа, изображённого справа вверху 46 граней. (Согласны?)

\textit{Планарным  графом}  называется граф, который можно изобразить на плоскости в виде плоского графа. Можно сказать, что планарный граф изоморфен некоторому плоскому графу.



\zn В связном графе \textbf{В}$= 10$, из каждой вершины выходит 3 ребра. Найдите \textbf{Р}. \lett  В плоском графе все 10 граней --- треугольники. Найдите \textbf{Р}.



\zp Шесть человек встали в круг. Оказалось, что каждый знаком с обоими своими соседями, а также с человеком, стоящим напротив него. Является граф знакомств этой компании планарным?




% \zn Как изменятся В, Р и Г, если убрать у графа вершину, из которой исходит только одно ребро? 
 %\lett Как изменятся В, Р и Г, если у графа убрать такое ребро, после убирания которого он останется связным?
 
\z У Наталии Павловны есть игра <<Туми иши>> из 16 многогранников. Как вы думаете:
\lett  для каждого ли из них соответствующий граф вершин и рёбер является планарным?
\lett  чего у каждого из  этих многогранников больше: рёбер, вершин или граней?

\medskip

\textbf{Формула Эйлера.} В любом плоском графе с \textbf{В} вершинами, \textbf{Р} рёбрами и \textbf{Г} гранями выполняется равенство \textbf{В}$-$\textbf{Р}$+$\textbf{Г}$=2$.


\medskip

%\noindent Можете взять коробку <<Туми иши>> для проверки вашей гипотезы.

\begin{wrapfigure}[9]{r}{.23\textwidth}\vspace{-.8cm}
    \includegraphics[width=\linewidth]{Listki/figs/zabory.jpg}
\end{wrapfigure}

\z Справа нарисованы дачные участки, разделённые 18 заборами. На каждом заборе между двумя участками сидит мальчишка. Рассмотрим два графа:\\
Граф (1): вершины --- это столбы (выделенные жирными точками), рёбра --- соединяющие их заборы.\\
Граф (2): вершины --- участки, а ребром соединены соседние участки. 
\lett Изобразите второй граф. Является ли он планарным?
\lett Как связаны между собой вершины, рёбра и грани двух этих графов и как связаны их количества?

\medskip

Граф (2) из  задачи \framebox{7} называется \textit{двойственным} к  плоскому графу (1). 

\medskip

\z Нарисуйте двойственные графы для \leth  всех деревьев с четырьмя вершинами; \lett  цикла с пятью вершинами;  \leth   любых двух правильных многогранников.

\zp Футбольный мяч сшит из 32 лоскутков: белых шестиугольников и чёрных пятиугольников. Каждый чёрный лоскут граничит только с белыми, а каждый белый --- с тремя чёрными и тремя белыми. Сколько лоскутков белого цвета?