Една графика се нарича плоска, ако може да бъде начертана в равнина, така че да няма пресичащи се ръбове.

Пример: Графиката, показана на фиг., е равнинна графика.

шехзад пунавала

Област на графика: Да разгледаме равнинна графика G=(V,E). Регионът се дефинира като област от равнината, която е ограничена от ръбове и не може да бъде допълнително разделена. Планарна графика разделя плановете на един или повече региони. Един от тези региони ще бъде безкраен.

Краен регион: Ако площта на областта е ограничена, тогава тази област се нарича крайна област.

Безкраен регион: Ако площта на региона е безкрайна, този регион се нарича безкраен регион. Равнинната графика има само една безкрайна област.

Пример: Разгледайте графиката, показана на фиг. Определете броя на регионите, крайните региони и един безкраен регион.

Решение: Има пет региона в горната графика, т.е. r₁,р₂,р₃,р₄,р₅.

Има четири крайни области в графиката, т.е. r₂,р₃,р₄,р₅.

Има само една крайна област, т.е. r₁

Свойства на равнинните графики:

1. Ако свързан равнинен граф G има e ребра и r области, тогава r ≦ То е.
2. Ако свързан равнинен граф G има e ребра, v върхове и r области, тогава v-e+r=2.
3. Ако свързан равнинен граф G има e ребра и v върхове, тогава 3v-e≧6.
4. Пълна графика К_не плоскост тогава и само ако n<5.< li>
5. Пълна двустранна графа K_мне планарна тогава и само ако m3.

Пример: Докажете, че пълната графика K₄е планарна.

Решение: Пълната графика К₄съдържа 4 върха и 6 ребра.

Знаем, че за свързана равнинна графика 3v-e≧6. Следователно за K₄, имаме 3x4-6=6, което удовлетворява свойството (3).

низ в java

Така К₄е равнинна графика. Следователно Доказано.

Неравнинна графика:

Казва се, че една графика не е равнинна, ако не може да бъде начертана в равнина, така че да няма кръстосани ръбове.

Пример: Графиките, показани на фиг., са неравнинни графики.

Тези графики не могат да бъдат начертани в равнина, така че да няма пресичащи ръбове, следователно те са неравнинни графики.

Свойства на неравнинни графики:

Един график е неравнинен тогава и само ако съдържа подграф, хомеоморфен на K₅или К_3.3

пълен суматор

Пример1: Покажете, че К₅е неравнинна.

Решение: Пълната графика К₅съдържа 5 върха и 10 ребра.

Сега, за свързан планарен график 3v-e≧6.

Следователно, за К₅, имаме 3 x 5-10=5 (което не удовлетворява свойство 3, защото трябва да е по-голямо или равно на 6).

По този начин К₅е неравнинна графика.

Пример2: Покажете, че графиките, показани на фиг., са неравнинни, като намерите подграф, хомеоморфен на K₅или К_3.3.

Решение: Ако премахнем ръбовете (V₁,IN₄),(IN₃,IN₄) и (V₅,IN₄) графиката G₁, става хомеоморфен на K₅.Следователно е неравнинен.

Ако премахнем ръба V_2,V7) графиката G₂става хомеоморфен на K_3.3.Следователно е неравнинен.

Оцветяване на графиката:

Да предположим, че G= (V,E) е графика без множество ребра. Оцветяването на върховете на G е присвояване на цветове на върховете на G, така че съседните върхове да имат различни цветове. Графа G е M-оцветяема, ако съществува оцветяване на G, което използва M-цветове.

Правилно оцветяване: Оцветяването е правилно, ако всеки два съседни върха u и v имат различни цветове, в противен случай се нарича неправилно оцветяване.

Пример: Разгледайте следната графика и оцветете C={r, w, b, y}. Оцветете правилно графиката, като използвате всички цветове или по-малко цветове.

Графиката, показана на фиг., е минимум 3-цветна, следователно x(G)=3

Решение: Фигура показва правилно оцветената графика с всичките четири цвята.

лента с инструменти за бърз достъп до ms word

Фигура показва графиката, правилно оцветена с три цвята.

Хроматично число на G: Минималният брой цветове, необходими за получаване на правилно оцветяване на графика G, се нарича хроматично число на G и се означава с x(G).

Пример: Хроматичното число на К_не n.

Решение: Оцветяване на К_нможе да се конструира с помощта на n цвята чрез присвояване на различни цветове на всеки връх. На два върха не могат да бъдат присвоени еднакви цветове, тъй като всеки два върха на този график са съседни. Оттук и хроматичното число на К_н=n.

Приложения за оцветяване на графики

Някои приложения на оцветяване на графики включват:

• Регистрирайте Разпределение
• Оцветяване на карта
• Проверка на двустранна графика
• Присвояване на мобилна радиочестота
• Изготвяне на разписание и др.

Изложете и докажете теоремата за ръкостискане.

Теорема за ръкостискане: Сумата от градусите на всички върхове в графа G е равна на удвоения брой ребра в графиката.

Математически може да се изрази като:

∑_v∈Vdeg(v)=2e

Доказателство: Нека G = (V, E) е графика, където V = {v₁, в₂, . . . . . . . . . .} е множеството от върхове и E = {e₁,То е₂. . . . . . . . . .} е множеството от ръбове. Знаем, че всяко ребро лежи между два върха, така че осигурява степен едно на всеки връх. Следователно всяко ребро допринася за степен две за графиката. Така сумата от градусите на всички върхове е равна на удвоения брой ръбове в G.

Следователно, ∑_v∈Vdeg(v)=2e

dateformat.format