Планарни графика - тя
Планарни Брой - брой, който може да се опише по равнина без пресичане ребра.
По-строго: Граф е поставен на повърхността, ако може да се възползва от него, без да преминават ръбове. Laid графика се нарича геометрична. срещата на върха е една точка в равнината, а билото линия върху него, областта, в която Графа разбива на повърхността, наречено лица. Плосък Ърл - Ърл, предвидена в самолета. Графиката се нарича планарна. ако е изоморфни на равнината графика.
Критерият за не-плоскостността
K5. пълен графика с 5 върховете
K3,3. графика, илюстрираща проблема на три ямки
- достатъчно условие - ако графиката има двустранен подграф K3,3 или K5 пълна подграф. това не е равнинна;
- необходимо условие - ако графиката не е равнинна, то трябва да съдържа повече от четири върховете на степен повече от 3 или по-голямо от 5 върховете на степен по-голяма от 2.
Теорема на Pontryagin-Kuratowski
Графика е равнинна единствено и само ако той не съдържа подграфи договорил да K5 или K3,3.
Формула на Ойлер
За свързан планарна графика следната зависимост между броя на върховете V, ръбове и изправена Д Е:
Ойлер в 1736 е намерено [1] в изследването на свойствата на изпъкнал polyhedra. Тази връзка се отнася и за други повърхности до коефициент, наречен Ойлер характеристика. Това инвариантна повърхност, самолет или сфера за това е равно на две.
Формулата има много полезни ефекти. От факта, че всеки аспект е ограничена от не повече от три ребра, че за планарна графика
т.е., с по-голям брой ръбове на известен nonplanar. (Обратното не е вярно например.) От това следва, че в планарна графика винаги може да се намери на връх степен най-много 5.
Равнинни графики в проблеми
Проблемът на три ямки. Има три къщи и три кладенеца. Това доказва, че е невъзможно, така че да се проправи пътя между къщите и кладенци, за всяка къща на всеки добре поддържан път, и няма две пътеки няма да се пресичат. (Не могат да бъдат изградени мостове.)
Оцветяване карти. Необходимо е да се боя плоска карта определен брой цветове, така че всеки две страни, които имат обща граница част имат различни цветове. Оказва се, че в отсъствието на анклави. винаги достатъчно четири цвята, но това твърдение е изключително трудно да се докаже, вижте. четири цвят теорема.
бележки
Вижте какво е "равнинна графика" в други речници:
EXTREME ГРАФИКА - графика на ром на един или друг цифров характеристика се минималната или максимална стойност. Обикновено се срещат екстремни стойности на определен числени характеристики на рояк и ограничения върху други числови характеристики и ... ... енциклопедия по математика
ГРАФИКА ПЛОСКА - равнинна графика, графиката способен правилно нагъната в равнина (виж колона подреждане.). С други думи, графиката G се нарича. плосък, ако той може да бъде представен в самолета, така че върховете съответстват на различни точки на самолета, както и линиите ... ... енциклопедия по математика
ГРАФИКА - много Vvershin и задайте Eneuporyadochennyh и нареди на двойки от върхове; определен чрез G.. Неподреден двойка върхове се нарича. ребро, подреден чифт дъга. G. съдържащ само ръбове, наречен. ненасочена; Г., съдържаща само дъгата ... ... енциклопедия по математика
ГРАФИКА двустранен - bichromatic графика, чиито набор от върха до бодното могат да бъдат разделени в две подгрупи несвързани, и. (Т ... енциклопедия по математика
Vertex (графика) - съдържа определения на теория графика. Курсив показват, препратки към условията в речника (на тази страница). # А Б В Г Д Е Ж З И Й К Л М Н О П Р Т U V ... Wikipedia
Планарни графика - равнинна графика графика, която може да бъде представена в равнина без преминаване ребра. По-строго: Граф е поставен на повърхността, ако може да се възползва от него, без да преминават ръбове. Laid графика се нарича геометрична ... Wikipedia
Ламан графика - В графика теория Lamanova графика с п върховете наричат тази графика G, че, от една страна, за всяка к всеки подграф на G, съдържащ к върхове, има не повече от 2k -3 ребра и второ, графиката G е точно 2n -3 ребра. Lamanova графики ... Wikipedia
Речник на теория на графите - съдържа определения на теория на графите. Курсив показват, препратки към условията в речника (на тази страница). # А Б В Г Д Е Ж З И Й К Л М Н О П Р ... Wikipedia
Дължината на диграфа - съдържа определения на теория графика. Курсив показват, препратки към условията в речника (на тази страница). # А Б В Г Д Е Ж З И Й К Л М Н О П Р Т U V ... Wikipedia