![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Определение. Граф называется плоским, если его можно изобразить на плоскости так, что никакие два ребра не будут пересекаться.Стр 1 из 8Следующая ⇒
Планарность графа
Определение Граф называется плоским, если его можно изобразить на плоскости так, что никакие два ребра не будут пересекаться.
Определение Граф называется планарным, если он изоморфен некоторому плоскому графу.
О планарных графах говорят, что они укладываются на плоскости. Если мы говорим об ориентированном графе, то он будет планарным, если планарен соответствующий ему неориентированный граф.
Пример Граф изоморфен графам 1
D
3 4 c d B C
Зачем нужна планарность? В радиоэлектронике при изготовлении микросхем печатным способом электрические цепи наносятся на плоскую поверхность изоляционного материала. А так как проводники не изолированы, то они не должны пересекаться. Аналогичная задача возникает при проектировании железных дорог, где нежелательны переезды.
Откуда возникла задача планарности? Решалась простая на первый взгляд задача: можно ли проложить дороги от домов к каждому колодцу, чтобы они не пересекались?
Позднее эта задача получила название задача о трех колодцах.
Определение Грань – это область, ограниченная непрерывной самонепересекающейся кривой, Такая кривая называется кривой Жордана. В графе всегда есть одна неограниченная грань и может быть сколько внутренних ограниченных граней.
Пример
4 1 – внешняя грань 1 2 – 2, 3, 4, 5 – внутренние области 2 3
Каждая грань ограничена, по крайней мере, тремя ребрами.
|