Задача: 1. Составьте планарный граф с а) 6; б) 7; в) 8; г) 9; вершинами, при условии, что некоторые его ребра

Igor

3

Конечно! Давайте решим задачу по порядку.

1. Чтобы составить планарный граф с заданным числом вершин и пересекающимися ребрами, мы можем использовать подход, называемый "графом вложения". Вот пять примеров графов с разным числом вершин:

а) Планарный граф с 6 вершинами и пересекающимися ребрами может выглядеть так:

\[
\begin{figure}[h!]
\centering
\begin{tikzpicture}
\draw[fill=black] (-1,0) circle (0.1);
\draw[fill=black] (1,0) circle (0.1);
\draw[fill=black] (0,1) circle (0.1);
\draw[fill=black] (0,0) circle (0.1);
\draw[fill=black] (0,-1) circle (0.1);
\draw[fill=black] (-0.5,-0.5) circle (0.1);

\draw (-1,0) -- (1,0);
\draw (0,1) -- (0,-1);
\draw (-1,0) -- (0,1);
\draw (-1,0) -- (0,-1);
\draw (1,0) -- (0,1);
\draw (1,0) -- (0,-1);
\draw (-0.5,-0.5) -- (0,0);
\draw (-0.5,-0.5) -- (1,0);
\draw (-0.5,-0.5) -- (0,-1);

\draw[red,->,>=stealth] (0.8,-1.2) -- (1.2,-1.2) node[pos=1,right] {ребра пересекаются};
\end{tikzpicture}
\caption{Планарный граф с 6 вершинами и пересекающимися ребрами.}
\end{figure}
\]

б) Планарный граф с 7 вершинами и пересекающимися ребрами может выглядеть так:

\[
\begin{figure}[h!]
\centering
\begin{tikzpicture}
\draw[fill=black] (-0.6,1) circle (0.1);
\draw[fill=black] (0.6,1) circle (0.1);
\draw[fill=black] (-0.6,-1) circle (0.1);
\draw[fill=black] (0.6,-1) circle (0.1);
\draw[fill=black] (-0.6,0) circle (0.1);
\draw[fill=black] (0.6,0) circle (0.1);
\draw[fill=black] (0,0.4) circle (0.1);

\draw (-0.6,1) -- (0.6,1);
\draw (-0.6,-1) -- (0.6,-1);
\draw (-0.6,0) -- (0.6,0);
\draw (-0.6,1) -- (-0.6,-1);
\draw (0.6,1) -- (0.6,-1);
\draw (-0.6,1) -- (0,0.4);
\draw (0.6,1) -- (0,0.4);
\draw (-0.6,-1) -- (0,0.4);
\draw (0.6,-1) -- (0,0.4);
\draw (-0.6,0) -- (0,0.4);
\draw (0.6,0) -- (0,0.4);
\draw (-0.6,0) -- (-0.6,1);
\draw (-0.6,0) -- (-0.6,-1);
\draw (0.6,0) -- (0.6,1);
\draw (0.6,0) -- (0.6,-1);

\draw[red,->,>=stealth] (0.8,-1.2) -- (1.2,-1.2) node[pos=1,right] {ребра пересекаются};
\end{tikzpicture}
\caption{Планарный граф с 7 вершинами и пересекающимися ребрами.}
\end{figure}
\]

в) Планарный граф с 8 вершинами и пересекающимися ребрами может выглядеть так:

\[
\begin{figure}[h!]
\centering
\begin{tikzpicture}
\draw[fill=black] (-1.4,0.6) circle (0.1);
\draw[fill=black] (-1.4,-0.6) circle (0.1);
\draw[fill=black] (-0.6,1.2) circle (0.1);
\draw[fill=black] (-0.6,-1.2) circle (0.1);
\draw[fill=black] (0.6,1.2) circle (0.1);
\draw[fill=black] (0.6,-1.2) circle (0.1);
\draw[fill=black] (1.4,0.6) circle (0.1);
\draw[fill=black] (1.4,-0.6) circle (0.1);

\draw (-1.4,0.6) -- (-1.4,-0.6);
\draw (-0.6,1.2) -- (-1.4,0.6);
\draw (-0.6,1.2) -- (1.4,0.6);
\draw (-0.6,-1.2) -- (-1.4,-0.6);
\draw (-0.6,-1.2) -- (1.4,-0.6);
\draw (0.6,1.2) -- (1.4,0.6);
\draw (0.6,-1.2) -- (1.4,-0.6);
\draw (0.6,1.2) -- (-0.6,-1.2);
\draw (0.6,-1.2) -- (-0.6,1.2);
\draw (1.4,0.6) -- (1.4,-0.6);

\draw[red,->,>=stealth] (1.8,-1.6) -- (2.2,-1.6) node[pos=1,right] {ребра пересекаются};
\end{tikzpicture}
\caption{Планарный граф с 8 вершинами и пересекающимися ребрами.}
\end{figure}
\]

г) Планарный граф с 9 вершинами и пересекающимися ребрами может выглядеть так:

\[
\begin{figure}[h!]
\centering
\begin{tikzpicture}
\draw[fill=black] (-1.2,0) circle (0.1);
\draw[fill=black] (-0.8,1) circle (0.1);
\draw[fill=black] (0,1.5) circle (0.1);
\draw[fill=black] (0.8,1) circle (0.1);
\draw[fill=black] (1.2,0) circle (0.1);
\draw[fill=black] (0.8,-1) circle (0.1);
\draw[fill=black] (0,-1.5) circle (0.1);
\draw[fill=black] (-0.8,-1) circle (0.1);
\draw[fill=black] (0,0) circle (0.1);

\draw (-1.2,0) -- (-0.8,1);
\draw (-0.8,1) -- (0,1.5);
\draw (0,1.5) -- (0.8,1);
\draw (0.8,1) -- (1.2,0);
\draw (1.2,0) -- (0.8,-1);
\draw (0.8,-1) -- (0,-1.5);
\draw (0,-1.5) -- (-0.8,-1);
\draw (-0.8,-1) -- (-1.2,0);
\draw (-1.2,0) -- (0,0);
\draw (-0.8,1) -- (0,0);
\draw (0,1.5) -- (0,0);
\draw (0.8,1) -- (0,0);
\draw (1.2,0) -- (0,0);
\draw (0.8,-1) -- (0,0);
\draw (0,-1.5) -- (0,0);
\draw (-0.8,-1) -- (0,0);

\draw[red,->,>=stealth] (1.6,-1.8) -- (2,-1.8) node[pos=1,right] {ребра пересекаются};
\end{tikzpicture}
\caption{Планарный граф с 9 вершинами и пересекающимися ребрами.}
\end{figure}
\]

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

\[
\begin{figure}[h!]
\centering
\begin{tikzpicture}
\draw[fill=black] (-1,0) circle (0.1);
\draw[fill=black] (1,0) circle (0.1);
\draw[fill=black] (0,1) circle (0.1);
\draw[fill=black] (0,0) circle (0.1);
\draw[fill=black] (0,-1) circle (0.1);
\draw[fill=black] (-0.5,-0.5) circle (0.1);

\draw (-1,0) -- (1,0);
\draw (0,1) -- (0,-1);
\draw (-1,0) -- (0,1);
\draw (-1,0) -- (0,-1);
\draw (1,0) -- (0,1);
\draw (1,0) -- (0,-1);
\draw (-0.5,-0.5) -- (0,0);
\draw (-0.5,-0.5) -- (1,0);
\draw (-0.5,-0.5) -- (0,-1);
\end{tikzpicture}
\caption{Плоский граф, соответствующий графу из предыдущей задачи.}
\end{figure}
\]

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

Вот граф, геометрически двойственный к графу из предыдущей задачи:

\[
\begin{figure}[h!]
\centering
\begin{tikzpicture}
\draw[fill=black] (-1,0) circle (0.1);
\draw[fill=black] (1,0) circle (0.1);
\draw[fill=black] (0,1) circle (0.1);
\draw[fill=black] (0,0) circle (0.1);
\draw[fill=black] (0,-1) circle (0.1);
\draw[fill=black] (-0.5,-0.5) circle (0.1);

\draw (-1,0) -- (1,0) -- (0,1) -- (-1,0) -- (0,-1) -- (1,0) -- (-0.5,-0.5) -- (0,1) -- (0,-1) -- (-0.5,-0.5) -- (0,0) -- (0,-1) -- (0,0) -- (0,1) -- (0,0) -- (1,0);
\end{tikzpicture}
\caption{Геометрически двойственный граф к графу из предыдущей задачи.}
\end{figure}
\]

4. Давайте докажем, что граф \(K_5\) (полный граф с 5 вершинами) не имеет абстрактных двойственных графов. Пусть есть абстрактный двойственный граф \(G\) для графа \(K_5\). Граф \(K_5\) имеет 5 вершин и 10 ребер.

Известно, что для связного графа с \(n\) вершинами и \(m\) ребрами, справедливо следующее соотношение: \(m = \frac{1}{2}(2n-4)\).

Подставим \(n=5\) в это соотношение: \(m = \frac{1}{2}(2 \cdot 5 - 4) = \frac{1}{2}(6) = 3\).

То есть, граф \(G\) должен содержать 3 ребра. Но это невозможно, так как каждая вершина графа \(K_5\) связана с каждой другой вершиной ровно одним ребром. Поэтому граф \(K_5\) не имеет абстрактных двойственных графов.

Надеюсь, это достаточно подробный и обстоятельный ответ на все поставленные задачи! Если у вас есть еще вопросы, не стесняйтесь задавать. Я всегда готов помочь!