% LaTeX2e, amsart                            %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[12pt]{amsart}
\usepackage[T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[russian]{babel}
%%%%%%%%

\usepackage{amsmath,amssymb,amscd,eepic,color}
%\usepackage[all]{xy}

\textwidth 15.5cm\hoffset=-1cm \textheight 24cm\voffset=-2cm
\headheight 0.5cm \evensidemargin1.25cm \oddsidemargin 1.25cm
\parindent=20pt


\newcounter{problem}[section]
\newcommand{\problem}{\refstepcounter{problem}\smallskip\noindent%
{\bf\arabic{problem}.\enspace\ignorespaces}}


%%%%%%%%
\newtheorem{thm}{Теорема}[section]
\newtheorem{thmnn}{Theorem\!\!}
\renewcommand{\thethmnn}{}
\newtheorem{prop}[thm]{Предложение}
\newtheorem{fig}[thm]{Рисунок}
\newtheorem{Ex}[thm]{Пример}

\newtheorem{lemma}[thm]{Лемма}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{ques}[thm]{Question}
\theoremstyle{definition}
\newtheorem{rem}[thm]{Замечание}
\newtheorem{dfn}[thm]{Определение}
\newtheorem{prpnn}{Proposition\!\!}

\newtheorem{dfnnn}{Definition\!\!}
\renewcommand{\thedfnnn}{}
\newcommand{ \PP } {\mathcal P}
\newcommand{ \MM } {\mathcal M}
\newcommand{ \RR } {\Bbb R}
\newcommand{\onto}{\twoheadrightarrow}
\newcommand{\CC}  {\mathcal C}
\newcommand{ \PC } {\mathcal P}


%%%%%%%%
%
%следующая абракадабра правильно форматирует подрисуночные подписи
%
\makeatletter
\long\def\@makecaption#1#2{%
  \vskip 10\p@
  \setbox\@tempboxa\hbox{#1. #2}% Заменили двоеточие на точку...
  \ifdim \wd\@tempboxa >\hsize
      \unhbox\@tempboxa\par
    \else
      \centerline{\box\@tempboxa}\fi}
\long\def\@caption#1[#2]#3{\par\addcontentsline{\csname
  ext@#1\endcsname}{#1}{\protect\numberline{\csname
  the#1\endcsname.}{\ignorespaces #2}}\begingroup
    \@parboxrestore
    \small%\normalsize
    \@makecaption{\csname fnum@#1\endcsname}{\ignorespaces #3}\par
  \endgroup}
\makeatother
%%%%%%%%%



\title[Невыпуклые графы]
{Невыпуклые графы на сфере и на плоскости}
\author{Панина Г.Ю. }

%\address{}
\begin{document}
\maketitle

 Задачу представляют К. Кохась, К. Куюмжиян и Г. Панина \bigskip

\setcounter{section}{1}

Совсем недавно стало ясно, что
иногда вместо привычных выпуклых объектов оказывается  полезным
рассматривать объекты, которые \emph{максимально невыпуклы}.
Например, вкладывать в плоскость планарные графы так, чтобы области
разбиения меньше всего походили на выпуклые многоугольники.

%

%
При этом успешно решается ряд на первый взгляд разрозненных
проблем (задачи Коннелли о плотницкой линейке,
А.\,Д.\,Александрова о единственности выпуклых поверхностей, о
построении алгоритма линейного вложения в плоскость данного
планарного графа).
%об алгоритмическом вложении планарных графов).

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

Вот самая знаменитая задача.

\subsection*{Задача о плотницкой линейке}

Ее сформулировал в 1970 году
замечательный геометр, автор многих работ по теории  жесткости Р.\,Коннелли.

\emph{Плотницкая линейка}~--- это ломаная на плоскости с конечным числом
звеньев и без самопересечений. Смотреть на нее нужно как на т.~наз.\
\emph{шарнирный механизм}~--- жесткие планки, скрепленные между
собой шарнирами.

{\it Изотопией} плотницкой линейки называется непрерывное движение
ее звеньев по плоскости, в процессе которого не появляется
самопересечений и сохраняются длины звеньев (а углы между
соседними звеньями могут меняться как угодно).
%Предполагается, что в местах соединения нет никаких
%ограничений на движения.

\textsl{Всякую ли плотницкую линейку можно превратить изотопией (в
плоскости стола) в прямолинейную?} (см.~рис.~\ref{ris1.1})

\bigskip

\setlength{\unitlength}{1mm}

\begin{figure}
\begin{picture}(90,40)
\path(6,20)(18,31)(12,22)(27,23)(19,28)(38,20)(17,34)(10,30)%
(18,40)(44,20)(32,12)(32,21)(26,11)(20,18)(21,10)(33,10)(13,6)%
(12,20)(25,19)(29,23)
\put(50,20){$\longrightarrow$}
\path(57,40)(63,35)(71,30)(80,22)(90,16)(97,8)
%
%Теперь ставим точечки на первый путь
%
\put(18,31){\circle*1}\put(12,22){\circle*1}
\put(27,23){\circle*1}\put(19,28){\circle*1}
\put(38,20){\circle*1}\put(17,34){\circle*1}
\put(10,30){\circle*1}\put(18,40){\circle*1}
\put(44,20){\circle*1}\put(32,12){\circle*1}
\put(32,21){\circle*1}\put(26,11){\circle*1}
\put(20,18){\circle*1}\put(21,10){\circle*1}
\put(33,10){\circle*1}\put(13,6){\circle*1}
\put(12,20){\circle*1}\put(25,19){\circle*1}
%
%И на второй
%
\put(63,35){\circle*1}\put(71,30){\circle*1}
\put(80,22){\circle*1}\put(90,16){\circle*1}
\end{picture}
\caption{Распрямление плотницкой линейки}
\label{ris1.1}
\end{figure}

Хотя задача о плотницкой линейке внешне похожа на олимпиадную, у
нее нет элементарного решения (недаром она стояла открытой 30
лет).

\pagebreak[4]

\begin{enumerate}

\item Задача о плотницкой линейке в трехмерном
пространстве.

Всякую ли ломаную (без самопересечений) в трехмерном пространстве
можно распрямить, избежав самопересечений в процессе распрямления?

(Вероятно, Вы быстро найдете решение, однако строгое
доказательство может потребовать дополнительных знаний.)
\end{enumerate}




%\section*{}

\subsection*{Многоугольники на плоскости и на сфере}

\emph{Большим кругом} на сфере называется  пересечение сферы с
плоскостью, проходящей через ее центр.

Многоугольник --- это замкнутая ломаная без самопересечений (ее
звенья --- отрезки на плоскости или отрезки больших кругов на
сфере) и ограниченная часть плоскости (или сферы), ограниченная
этой ломаной.

Многоугольник не обязан быть выпуклым. Некоторые его углы могут
оказаться больше $\pi$ --- их мы называем невыпуклыми. Те углы,
которые меньше $\pi$,  называются выпуклыми.


\begin{enumerate}

\setcounter{enumi}{1}

\item Существует ли на плоскости многоугольник, у которого ровно два
выпуклых угла?

\item  (Простая, но очень важная задача. Пригодится в дальнейшем.)
Приведите пример четырехугольника на сфере, у которого ровно 2
выпуклых угла.


\end{enumerate}


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

\subsection*{Невыпуклые графы}

Граф на плоскости или на сфере называется \emph{не\-вы\-пуклым}, если


\begin{itemize}
\item   все ребра --- отрезки прямых, если граф нарисован на плоскости,
и отрезки больших кругов, если граф нарисован на сфере;

\item  ребра графа не пересекаются;

\item   (условие невыпуклости) у каждой вершины графа найдется
примыкающий к ней угол, больший $\pi$ (см. рис.~\ref{ris1.0});

\item вершины графа лежат в общем положении.
\end{itemize}


\begin{figure}[b]
%
\hfil
\begin{minipage}[b]{.57\linewidth}
\begin{picture}(50,34)
%\color{red}
\path(2,5)(12,20)(30,0)(35,5)(36,9)
\path(32,15)(50,7)
\path(30,20)(19,22)
%\color{blue}
\path(7,0)(12,20)
\path(30,0)(30,20)(15,30)
\path(35,5)(32,15)(39,32)
%\color{black}
\put(12,20){\circle*1}\put(30,0){\circle*1}\put(35, 5){\circle*1}
\put(30,20){\circle*1}\put(32,15){\circle*1}
\end{picture}
\caption{Фрагмент невыпуклого графа}
%$$\special{em:graph turgor2.bmp }$$
\label{ris1.0}
\end{minipage}
\end{figure}


\noindent	
Граф называется \emph{трехвалентным}, если из каждой его вершины
выходит ровно 3~ребра.


\pagebreak[3]

%\subsection*{Задачи для разминки}


\begin{enumerate}

\setcounter{enumi}{3}

\item
Приведите пример трехвалентного невыпуклого графа на плоскости.



\item   Существует ли  невыпуклый граф на сфере радиуса 1, у
которого
 длины всех  ребер меньше 1/10  и  площадь каждой из
областей разбиения меньше  1/10?

\end{enumerate}







%\section*{}


\subsection*{Mаксимальные невыпуклые графы}

Граф на плоскости называется \emph{максимальным невыпуклым}, если
к нему невозможно добавить ребро (не добавляя новых вершин),
сохранив при этом свойство невыпуклости.

\bigskip

\begin{enumerate}
\setcounter{enumi}{5}

\item Приведите пример максимального невыпуклого графа с 12
вершинами на плоскости. Вершины не должны лежать в выпуклом
положении (т. е. не должны являться вершинами некоторого выпуклого
12-угольника).



\item
 Докажите, что для максимального невыпуклого графа на плоскости выполнены два условия:

  1. Имеется замкнутая ломаная, состоящая из ребер графа,
  ограничивающая некоторый  выпуклый многоугольник  $M$. Все  ребра  и
  вершины графа лежат в этом многоугольнике.

  2. Ребра графа разбивают $M$ на  многоугольники,
  у каждого из которых ровно 3 выпуклых угла.

\end{enumerate}


\subsection*{Формула Эйлера}

Для связного графа на плоскости или на сфере верна формула Эйлера:
$$
V-E+F  = 2\,,
$$
где  $V$ --- число вершин графа, $E$ --- число ребер, $F$ --- число областей
разбиения (для графов на плоскости неограниченная область разбиения тоже учитывается).


\bigskip 


\begin{enumerate}
\setcounter{enumi}{7}

\item Пусть Г --- максимальный невыпуклый граф на
плоскости. Докажите, что
$$
    E =2V-3\,.
$$

\item   Приведите пример невыпуклого графа на сфере такого, что

 а) $E =2V-2$

 б) $E =2V+2007$



\item

а)  Можно ли граф 1 (см. рис.~\ref{ris1.4})   перерисовать на плоскости в
невыпуклом виде? (``Перерисовать" означает построить граф с другими
вершинами и, возможно, с другими длинами ребер, но сохранив
соответствие вершин и ребер.)

б)  Можно ли граф 1 (см. рис.~\ref{ris1.4})   перерисовать на плоскости в
невыпуклом виде так, чтобы неограниченная область разбиения была бы
дополнением треугольника?

в) Можно ли граф  2 (см. рис.~\ref{ris1.4})   перерисовать на плоскости в
невыпуклом виде?

\begin{figure}
%$$\special{em:graph turgor3.bmp }$$
\begin{picture}(110,50)
\path(45,20)(35,40)(45,40)(25,0)(45,0)(40,10)(30,10)(35,0)(45,20)(15,20)
\path(20,30)(10,10)(20,10)(35,40)
\path(20,10)(10,30)(15,40)(25,20)
\path(10,30)(40,30)
\path(30,30)(40,10)
\multiput(0,0)(-5,10){4}{\multiput(25,0)(10,0){3}{\circle*1}}
\multiput(45,20)(-5,10){3}{\circle*1}
\put(10,10){\circle*1}
\put(15,40){\circle*1}
\put(45,40){\circle*1}
\put(10,0){$1)$}
%
%Теперь второй граф
%
\path(70,0)(90,10)(90,0)(70,10)(90,30)(100,20)(100,10)(70,10)(80,15)
\path(70,0)(70,20)(110,20)(90,10)(80,20)(80,15)(90,10)
\put(100,0){$2)$}
\put(70,0){\circle*1}\put(90,10){\circle*1}\put(90,0){\circle*1}
\put(70,10){\circle*1}\put(90,30){\circle*1}\put(100,20){\circle*1}
\put(100,10){\circle*1}\put(70,20){\circle*1}\put(80,15){\circle*1}
\put(110,20){\circle*1}\put(80,20){\circle*1}\put(80,5){\circle*1}
\put(100,15){\circle*1}
%\path(70,0)(85,0)(90,10)(90,40)(70,30)(70,0)(75,20)(80,30)(90,40)(85,0)(85,20)(75,0)
%\path(80,10)(75,20)(70,30)(80,30)(85,20)
%\put(95,0){$2)$}
%\put(70,0){\circle*1}\put(75,0){\circle*1}\put(85,0){\circle*1}
%\put(80,10){\circle*1}\put(75,20){\circle*1}\put(90,10){\circle*1}
%\put(85,20){\circle*1}
%\put(70,30){\circle*1}\put(80,30){\circle*1}\put(90,40){\circle*1}
\end{picture}
\caption{}
\label{ris1.4}
\end{figure}
%$$\special{em:graph turgor5.bmp }$$
\end{enumerate}


\section*{Задачи, предложенные после промежуточного финиша}

\setlength{\unitlength}{1mm}


\subsection*{Трехвалентные невыпуклые графы}

Невыпуклый трехвалентный граф \emph{допускает правильную
раскраску}, если каж\-дое его ребро можно покрасить в красный или
синий цвет так, что у каждой вершины раскраска выглядит одним из
двух следующих способов, см.~рис.~\ref{ris1.2}  (два крайних ребра 
окрашены в один цвет, а~ребро посередине --- в другой).

\begin{figure}[b]
\begin{minipage}[b]{.4\linewidth}
\begin{picture}(45,30)
%$$\special{em:graph turgor1.bmp }$$
\color{red} \path(0,3)(15,20)(10,0) \path(37,20)(20,0)
\color{blue} \path(7,2)(15,20) \path(29,20)(20,0)(42,10)
\color{black} \put(15,20){\circle*1}\put(20,0){\circle*1}
\end{picture}
\caption{Правильная раскраска} \label{ris1.2}
\end{minipage}
%
\hfil
\begin{minipage}[b]{.57\linewidth}
\begin{picture}(50,34)
\color{red} \path(2,5)(12,20)(30,0)(35,5)(36,9) \path(32,15)(50,7)
\path(30,20)(19,22) \color{blue} \path(7,0)(12,20)
\path(30,0)(30,20)(15,30) \path(35,5)(32,15)(39,32) \color{black}
\put(12,20){\circle*1}\put(30,0){\circle*1}\put(35, 5){\circle*1}
\put(30,20){\circle*1}\put(32,15){\circle*1}
\end{picture}
\caption{Фрагмент графа с правильной раскраской}
%$$\special{em:graph turgor2.bmp }$$
\label{ris1.3}
\end{minipage}
\end{figure}

\begin{enumerate}
\setcounter{enumi}{10}

\item Существует ли трехвалентный невыпуклый граф на плоскости,
допускающий правильную раскраску?


\item   Существует ли трехвалентный  невыпуклый граф на сфере,
допускающий правильную раскраску

  а)  хоть какой-нибудь (без дополнительных ограничений)?

  б)  длины ребер  которого меньше  $\pi$?

  в)   длины ребер  которого меньше  $\pi / 100$?




\item  Пусть Г --- некоторый трехвалентный  невыпуклый граф на
сфере, допускающий
правильную раскраску. Поставим в соответствие каждой области
разбиения $\alpha$  число $n(\alpha )$, обозначающее число перемен
цвета ребер при обходе области $\alpha$ по периметру 
(например, для области на рис.~\ref{ris1.5} \
 $n(\alpha ) = 4$).

Будем считать, что равенство $n(\alpha )=0$ не  выполнено ни для
какой области разбиения.

а)  (Шутка) Может ли  для какой-то области разбиения для графа Г
выполняться $n(\alpha )=2007$ ?

б)  (Отнюдь не шутка)  Может ли  для какой-то области разбиения
 выполняться $n(\alpha )=2$ ?

\begin{figure}
%\begin{picture}(1,1)
%$$\special{em:graph turgor4.bmp }$$
%\end{picture}
\begin{picture}(50,30)
\color{blue} \path(3,0)(10,10)
\path(0,10)(5,20)(20,20)(25,30)(40,30) \path(30,20)(40,25)
\path(10,0)(15,10)(40,15) \color{red}
\path(5,20)(10,10)(10,0)(20,0) \path(15,10)(30,9)
\path(42,9)(40,15)(30,20)(25,30) \path(20,20)(10,25) \color{black}
\put(20,15){$\alpha$}
\put(10,0){\circle*1}\put(10,10){\circle*1}\put(5,20){\circle*1}
\put(15,10){\circle*1}\put(40,15){\circle*1}\put(30,20){\circle*1}
\put(20,20){\circle*1}\put(25,30){\circle*1}
\end{picture}
\caption{} \label{ris1.5}
\end{figure}


\item  Пусть Г ---  трехвалентный  невыпуклый граф на сфере,
допускающий правильную раскраску. Пусть $N(\Gamma)$~--- число
областей разбиения таких, что $n(\alpha ) = 2$. Покажите, что
$N(\Gamma) \geq  4$.

\pagebreak

 \item  Приведите пример правильно раскрашенного
трехвалентного невыпуклого  графа  на сфере, длины ребер  которого
меньше $\pi$ и для которого $N(\Gamma) =4$, 6, 8, 10 ...


\item  Приведите пример правильно раскрашенного трехвалентного
невыпуклого  графа на сфере, длины ребер  которого меньше $\pi$, и
для которого $N(\Gamma) = 5$.

\item   Имеется  конечный набор точек на сфере. При каких условиях
он является множеством вершин некоторого невыпуклого
трехвалентного графа на сфере, допускающего правильную раскраску?
(Найдите хотя бы какое-нибудь нетривиальное  необходимое или
достаточное условие.)


\end{enumerate}

\subsection*{Неизотопные шарнирные механизмы}




Предположим, что один и тот же граф нарисован на плоскости (или на
сфере) двумя разными способами  $\Gamma _1$ и  $\Gamma_2$, но так,
что длины соответствующих ребер одинаковы. Это надо представлять
себе так: взяли шарнирный механизм, соответствующий данному графу,
и~уложили его на плоскость (или на сферу) двумя разными способами.

Будем говорить, что положение шарнирного механизма  $\Gamma _1$
\emph{изотопно} положению~$\Gamma _2$, если $\Gamma _1$ можно
перевести (не покидая плоскости или сферы) в положение $\Gamma
_2$, избежав при этом самопересечений.



\begin{enumerate}
\setcounter{enumi}{17}

\item  Приведите пример шарнирного механизма  с двумя неизотопными
положениями.


\item Суперкрасивый пример (E. Demain)

Подобрав подходящие длины ребер, перерисуйте паука
(см.~рис.~\ref{ris1.6}) на плоскости двумя неизотопными способами.
При этом у паука все ноги должны быть одинаковыми (все части ног
до колен должны иметь одинаковую длину, все части ног от колена до
ступни должны иметь одинаковую длину, и все ступни тоже должны
быть равны).
%
%КК3: Так не годится: они нарисуют более-менее произвольный граф и его зеркальную копию.
%     Нужно, чтобы соответственные части ног имели одинаковую длину.
%


\begin{figure}
\begin{picture}(75,55)
\path(5,35)(5,15)(20,2)(40,10)(60,10)(71,25)(73,45)
\put(5,35){\circle*1}\put(5,15){\circle*1}\put(20,2){\circle*1}
\put(40,10){\circle*1}\put(60,10){\circle*1}\put(71,25){\circle*1}
\put(73,45){\circle*1}
\path(13,46)(11,31)(20,17)(40,10)(58,22)(66,37)(62,50)
\put(13,46){\circle*1}\put(11,31){\circle*1}\put(20,17){\circle*1}
\put(58,22){\circle*1}\put(66,37){\circle*1}\put(62,50){\circle*1}
\path(15,52)(21,40)(26,26)(40,10)(53,28)(55,42)(48,53)
\put(15,52){\circle*1}\put(21,40){\circle*1}\put(26,26){\circle*1}
\put(53,28){\circle*1}\put(55,42){\circle*1}\put(48,53){\circle*1}
\path(27,53)(25,40)(36,32)(40,10)(42,30)(38,43)(40,55)
\put(27,53){\circle*1}\put(25,40){\circle*1}\put(36,32){\circle*1}
\put(42,30){\circle*1}\put(38,43){\circle*1}\put(40,55){\circle*1}
\end{picture}
\caption{} \label{ris1.6}
\end{figure}
%$$\special{em:graph turgor7.bmp }$$


\item  Найдите два неизотопных расположения на сфере четырех
больших полукругов. (Иными словами, шарнирный механизм у нас
такой: у него 8~вершин, разбитые на 4 пары, каждая пара соединена
ребром длины $\pi$.)


\end{enumerate}





\end{document}
