Графи - задачи за познанства

[Мирослав Стоенчев]

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

[Реклама]

[Мирослав Стоенчев]

Оцветяване на Графи

Дефиниция.Под граф ще разбираме множество от точки, някои от които са свързани с дъги.Точките ще наричаме върхове на графа, а дъгите - ребра на графа.Ако всеки два върха на графа са свързани с ребра, ще казваме, че графа е пълен.

Да разгледаме следната интерпретация: Нека е дадена [tex]n-[/tex] членна компания.Хората ще ги изобразяваме като върхове на граф, а познанствата между отделните членове чрез ребра. Например, ако [tex]A[/tex] и [tex]B[/tex] се познават - свързваме ги чрез ребро, ако не се познават, не ги свързваме.

Дефиниция.За два върха на графа ще каваме, че са съседни, ако са съединени с ребро. За две ребра на графа ще казваме, че са съседни, ако имат общ връх.

Дефиниция.Двата върха на всяко ребро наричаме краища на реброто.

Елементи на Граф: Върхове и ребра, [tex]G=\left\{v|v\in G\right\}\cup\left\{e|e\in G\right\}.[/tex] Тук представихме графа [tex]G[/tex] kaто обединение на множеството [tex]\left\{v|v\in G\right\}[/tex] от върховете му, и множеството [tex]\left\{e|e\in G\right\}[/tex] от ребрата му.

Дефиниция.Ако [tex]v\in G[/tex] е връх на графа, то броя на съседните му върхове ще означаваме с [tex]d_{v}.[/tex] Числото [tex]d_{v}[/tex] ще наричаме степен на върха [tex]v.[/tex] Най-голямата от степените на върховете на графа се нарича степен на графа [tex]G,[/tex] ще я означим с [tex]d(G).[/tex] T.e. [tex]d(G)=\max_{v}\left\{d_{v}|v\in G\right\}.[/tex]

Дефиниция.Множеството от върховете на графа [tex]G,[/tex] всеки два от които са съседни, ще наричаме клика. Ако броя на върховете от кликата е [tex]k,[/tex] то ще я наричаме [tex]k-[/tex] клика.

Така 2-кликите са ребрата, 3-кликите са триъгълници, а понякога 4-кликите се наричат тетраедри.

Дефиниция.Ако в [tex]G[/tex] има [tex]s-[/tex]клика, но няма [tex]s+1-[/tex]клика, то ще казваме, че [tex]G[/tex] има кликово число [tex]s.[/tex] Последното го записваме така [tex]cl(G)=s.[/tex]

Дефиниция.Множеството [tex]A[/tex] от върхове на [tex]G,[/tex] никои два от които не са съседни, ще наричаме независимо множество.Ако в [tex]G[/tex] има независимо множество с [tex]s[/tex] върха, но няма такова с [tex]s+1[/tex] върха, ще казваме, че [tex]G[/tex] има число на независимост [tex]s.[/tex] Записваме го така [tex]\alpha(G)=s.[/tex]

Пълния граф с [tex]n-[/tex] върха ще означаваме с [tex]K_{n}.[/tex]

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

[Мирослав Стоенчев]

Подграф

Нека [tex]G[/tex] и [tex]H[/tex] са два графа. Ще казваме, че [tex]G[/tex] е подграф на [tex]H,[/tex] ако всеки връх на [tex]G[/tex] е връх и на [tex]H[/tex] и всяко ребро на [tex]G[/tex] е ребро на [tex]H.[/tex] В такъв случай ще казваме, че [tex]H[/tex] съдържа [tex]G.[/tex]

Вериги

Нека [tex]v_{1},v_{2},...,v_{k}[/tex] е редица от върхове на графа [tex]G.[/tex] Да приемем, че [tex]\left\(v_{i},v_{i+1}\right\)[/tex] са свързани с ребро за [tex]i=1,2,...,k-1.[/tex] Тогава редицата от върхове [tex]v_{1},v_{2},...,v_{k}[/tex] на [tex]G[/tex] ще я наричаме верига в [tex]G[/tex] с дължина [tex]k-1.[/tex]
Веригата се нарича затворена, ако [tex]v_{1}=v_{k}.[/tex]
Проста верига- ако всички върхове участаващи във веригата са различни, евентуално с изключение на [tex]v_{1},v_{k}.[/tex]

Дефиниция. Проста затворена верига ще наричаме цикъл.Цикъл с дължина [tex]k[/tex] ще означаваме с [tex]C_{k}.[/tex]

Дефиниция. Дължината на най-късата проста верига съединяваща два върха(ако съществува) се нарича разстояние между двата върха.

Дефиниция. Един граф наричаме свързан, ако всеки два негови върха са съединени с верига.

[Мирослав Стоенчев]

Теорема на Туран. Ако граф [tex]G[/tex] с [tex]n[/tex] върха има повече от [tex]\frac{n^2}{4}[/tex] ръба, то [tex]G[/tex] съдържа поне един триъгълник.

Теорема на Радемахер. Ако граф [tex]G[/tex] с [tex]n[/tex] върха има повече от [tex]\frac{n^2}{4}[/tex] ръба, то [tex]G[/tex] съдържа поне [tex]\left\[\frac{n}{2}\right\][/tex] триъгълника.

Теорема на Гудмен. Всеки ръб на пълния граф [tex]G[/tex] с [tex]n[/tex] върха е оцветен с черен или бял цвят. Да се докаже, че за броя [tex]t(n)[/tex] на едноцветните триъгълници е в сила: [tex]t(n)\ge \begin{tabular}{|l}2{k\choose 3},\ n=2k\\\frac{2k(k-1)(4k+1)}{3},\ n=4k+1\\\frac{2k(k-1)(4k-1)}{3},\ n=4k+3 \end{tabular} [/tex]


Дефиниция. Нека [tex]p,q\in N.[/tex] Да означим с [tex]R(p,q)[/tex] най-малкото естествено число [tex]n[/tex] притежаващо свойството: при всяко оцветяване в два цвята(бял,черен) на ребрата на пълен граф [tex]G[/tex] с [tex]n[/tex] върха, то [tex]G[/tex] съдържа или черна [tex]p-[/tex] клика, или бяла [tex]q-[/tex] клика.

Числата [tex]R(p,q)[/tex] се наричат числа на Ремзи. Пресметнати са някои от тези числа: [tex]R(3,3)=6,\ R(3,4)=9,\ R(3,5)=14,\ R(3,6)=18,\ R(3,7)=23,\ R(4,4)=18.[/tex]

Информация относно конкретни числа на Ремзи може да прочетете тук: http://mathworld.wolfram.com/RamseyNumber.html

[Who_cares123456]

Неравенство на Ердьош-Секереш :
R(m,n)[tex]\le [/tex]R(m-1,n)+R(m,n-1)

[Gringo]

Материалът кога се взима в училище?

[estoyanovvd]

[evgeni91]

[krassi_holmz]

[estoyanovvd]

Или школа по математика, да речем, към училището в което учиш!!!