Планарний граф - це

Планарний граф - граф. який може бути зображений на площині без перетину ребер.

Більш строго: Граф укладається на деякій поверхні, якщо його можна на ній намалювати без перетину ребер. Укладений граф називається геометричним. його вершини - це точки площині, а ребра - лінії на ній. Області, на які граф розбиває поверхню, називаються гранями. Плоский граф - граф, покладений на площину. Граф називається планарним. якщо він ізоморфний деякому плоскому графу.

Два приклади непланарних графів

Тут ми користуємося інтуїтивним поняттям слова «лінія», докладніше див. У відповідній статті.

Повний граф з п'ятьма вершинами

K5. повний граф з 5 вершинами

Дивитися що таке "Планарний граф" в інших словниках:

ГРАФ ПЛОСКИЙ - планарний граф, граф, що допускає правильну укладку на площині (див. Графа укладання). Іншими словами, граф G зв. плоским, якщо він може бути зображений на площині так, що вершин відповідають різні точки площини, а лінії, ... ... Математична енциклопедія

Граф Петерсена - Цю статтю слід вікіфіціровать. Будь ласка, оформіть її згідно з правилами оформлення статей ... Вікіпедія

Плоский граф - Планарний граф граф, який може бути зображений на площині без перетину ребер. Більш строго: Граф укладається на деякій поверхні, якщо його можна на ній намалювати без перетину ребер. Укладений граф називається геометричним, його ... Вікіпедія

Вершина (граф) - Тут зібрані визначення термінів з теорії графів. Курсивом виділено посилання на терміни в цьому словнику (на цій сторінці). # А Б В Г Д Е Е Ж З И Й К Л М Н О П Р С Т У Ф ... Вікіпедія

Двочастковий граф - Біграф двочастковий граф або біграф це математичний термін теорії графів, що позначає граф, безліч вершин якого можна розбити на дві частини таким чином, що ка ... Вікіпедія

Планарність - Планарний граф граф, який може бути зображений на площині без перетину ребер. Більш строго: Граф укладається на деякій поверхні, якщо його можна на ній намалювати без перетину ребер. Укладений граф називається геометричним, його ... Вікіпедія

Теорія графів - Граф з шістьма вершинами і сім'ю ребрами Теорія графів розділ дискретної математики, що вивчає властивості графів. У загальному сенсі граф представляється як безліч вершин (вузлів), з'єднаних ребрами. У строго ... Вікіпедія