Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






  • Как продвинуть сайт на первые места?
    Вы создали или только планируете создать свой сайт, но не знаете, как продвигать? Продвижение сайта – это не просто процесс, а целый комплекс мероприятий, направленных на увеличение его посещаемости и повышение его позиций в поисковых системах.
    Ускорение продвижения
    Если вам трудно попасть на первые места в поиске самостоятельно, попробуйте технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Если ни один запрос у вас не продвинется в Топ10 за месяц, то в SeoHammer за бустер вернут деньги.
    Начать продвижение сайта
  • Определение. Граф называется плоским, если его можно изобразить на плоскости так, что никакие два ребра не будут пересекаться.






    Планарность графа

     

    Определение

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

     

    Определение

    Граф называется планарным, если он изоморфен некоторому плоскому графу.

     

    О планарных графах говорят, что они укладываются на плоскости.

    Если мы говорим об ориентированном графе, то он будет планарным, если планарен соответствующий ему неориентированный граф.

     

    Пример

    Граф изоморфен графам

    1 2 a b A

     
     

     


    D

     

    3 4 c d B C

     

    Зачем нужна планарность?

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

    Аналогичная задача возникает при проектировании железных дорог, где нежелательны переезды.

     

    Откуда возникла задача планарности?

    Решалась простая на первый взгляд задача: можно ли проложить дороги от домов к каждому колодцу, чтобы они не пересекались?

     

    Позднее эта задача получила название задача о трех колодцах.

     

    Определение

    Грань – это область, ограниченная непрерывной самонепересекающейся кривой, Такая кривая называется кривой Жордана.

    В графе всегда есть одна неограниченная грань и может быть сколько внутренних ограниченных граней.

     

    Пример

     

    4 1 – внешняя грань

    1 2 – 2, 3, 4, 5 – внутренние области

    2 3

     

    Каждая грань ограничена, по крайней мере, тремя ребрами.

     






    © 2023 :: MyLektsii.ru :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.