Как называется плоский объект ограниченный ребрами?

Корпус , жёсткий диск .

Граф, изображенный на плоскости, называется плоским графом, если его ребра не пересекаются в точках, отличных от вершин графа. заметим, что данное понятие касается только изображения графа, но не графа как множества вершин и связей. часто один и тот же граф может быть изображён как плоский, так и как не плоский. важное практическое приложение плоских графов - прокладка коммуникаций между объектами при условии, что пересечение коммуникаций нежелательно. теперь об одном важном свойстве плоских графов. сначала важное понятие. гранью в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов. заметим, что часть плоскости, лежащая "вне" фигуры графа, также подходит под определение грани и считается гранью. при определении граней графа нужна осторожность - опасно пренебрегать выражением "не содержащая других циклов" в определении термина. так, на рис. 2 область 2-4-3-5-2 не является гранью - она ограничена простым циклом, но сама содержит простой цикл 2-3-5-2. теперь собственно свойство. пусть в - количество вершин в графе, г - количество граней в плоском представлении графа, р - количество рёбер в графе. тогда получаем формулу эйлера: в + г - р = 2 для связного графа. для несвязного графа с k компонентами связности формула имеет вид в + г - р = k + 1. подставьте в неё k=1 и сравните с предыдущей. интересное совпадение, не правда ли? формула эйлера для выпуклых многогранников также заметим, что формула эйлера выполняется для выпуклых многогранников. и это не случайно: выпуклый многогранник может быть представлен как плоский граф, если вершины и рёбра многогранника рассматривать как вершины и рёбра графа. теперь покажем это на деле: возьмём n-угольную пирамиду с выпуклым многоугольником в основании и "превратим" её в плоский граф (см. рис. 3). у пирамиды n+1 граней (основание и n боковых граней), n+1 вершин (n в основании и одна "обособленная") и 2n рёбер (n в основании и n соединяющих "обособленную" вершину" с остальными). легко проверить - формула эйлера тут работает. теперь разберёмся с плоским графом на рис. 3 справа. аналогично несложно понять, что имеются n+1 вершин и 2n рёбер. теперь разберёмся с гранями. их опять n+1 (n граней-треугольников и "внешняя" грань вне фигуры). снова формула эйлера работает: n+1+n+1-2n=2. сейчас похожий фокус проделаем с n-угольной призмой. имеем n+2 граней (два основания и n боковых граней), 2n вершин (по n вершин в каждом основании) и 3n рёбер (по n в каждом основании и ещё n соединяющих основания). получаем b + г - р = 2. теперь разбираемся с графом. количество вершин и рёбер считается легко. граней снова n+2: "внутренний" n-угольник, n четырехугольников и "внешняя" грань. и снова формула эйлера работает. планарные графы и проверка на планарность планарный граф - граф, который может быть изображён как плоский. пример планарного графа: не всякий граф является планарным графом. согласно теореме куратовского-понтрягина (иногда её также называют теоремой понтрягина-куратовского, а иногда и вовсе опускают одну из фамилий), граф планарен тогда и только тогда, когда он не содержит подграфов типов, на рис. 6. на основе теоремы куратовского-понтрягина просто получить один примечательный вид непланарных графов. поскольку полный граф с 5 вершинами непланарен, а полный граф с n> 5 вершинами содержит такой подграф, то верно следующее. полный граф с n> 4 вершинами обязательно непланарен. на первый взгляд кажется, что всё просто - у нас лишь два типа "вредных" подграфов. на самом же деле анализа большого графа на наличие таких подграфов весьма непроста. одним из алгоритмов, проверяющих, планарен ли граф, является алгоритм, разработанный в 1970г. хопкрофтом и тарьяном и улучшенный ими в 1974г. алгоритм работает за линейное время.

// pascalabc.net 3.3, сборка 1555 от 21.10.2017 // внимание! если программа не работает, обновите версию! begin   var a: =arrrandom(readinteger('n=',50); a.println;   writeln('среднее значение равно ',a.average); end. пример n= 15 -50 -39 -10 49 35 -11 -34 34 -28 37 45 45 -24 42 2 среднее значение равно 6.2