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

 

 

Рис. 1

А всегда ли можно так изобразить любой граф на плоскости, чтобы его ребра не пересекались? Впервые этот вопрос возник при решении старой головоломки. Вот как ее описывает Льюис Кэрролл. В трех домиках жили три человека, неподалеку находилось три колодца: один с водой, другой с маслом, а третий с повидлом. Однако хозяева домиков перессорились и решили провести тропинки от своих домиков к колодцам так, чтобы эти тропинки не пересекались. Первоначальный вариант, изображенный на рис. 2, по этой причине их не устраивал.

 

Рис. 2

На рис. 2 изображена очередная попытка проложить тропинки, на которых осталась непроведенной только одна тропинка.

Графы, которые можно изобразить на плоскости без пересечения их ребер, принято называть плоскими.

Если немного подумать, то можно доказать, что граф «домики-колодцы» с шестью вершинами не является плоским. Не плоский и граф с пятью вершинами, каждые из которых соединены ребром (рис.3).

 Рис. 3

 Эти два графа, как оказалось, играют очень важную роль в определении того — является ли данный граф плоским. Оказывается, что если граф не плоский, то в нем «сидит» или граф «домики-колодцы» или «полный пятивершинник» (рис.3). Эту теорему независимо друг от друга доказали польский математик К.Куратовский и наш академик Л.С.Понтрягин.

Плоские графы разбивают плоскость на куски, как границы государств разбивают поверхность Земли. Любопытно, что между количеством вершин — В, количеством ребер — Р и количеством стран — Г плоского графа существует простое соотношение: В — Р + Г - 1

Если же к странам отнести и внешность графа — бесконечную страну, то формула будет иметь вид: В — Р + Г = 2

Рис. 4



Эта формула будет верна для любого выпуклого многогранника, где В, Р, и Г — количество его вершин, ребер и граней. Например, у куба В = 8, Р = 12, Г = 6 и мы имеем:

8 — 12 + 6 = 2.

Вершины и ребра многогранников, очевидно, образуют графы, причем для выпуклых многогранников (и не только для них) эти графы будут плоскими. На рис.4 изображены графы, соответствующие правильным многогранникам. На них вы можете проверить справедливость формулы. Она была открыта Леонардом Эйлером, но выяснилось, что для многогранников она была известна еще Рене Декарту.

Частные мастера Винтовые лестницы на второй этаж

Дренажная система водоотвода вокруг фундамента - stroidom-shop.ru

Правильное создание сайтов в Киеве https://atempl.com/r/