Chcâc przybliûyê czytelnikom Fat Agnusa jednâ z ciekawszych dziedzin informatyki, jakâ jest niewâtpliwie teoria grafów, pozwoliîem sobie ôciâgnâê z sieci artykuî omawiajâcy, oczywiôcie w zarysie, najwaûniejsze jej elementy.
Serious mode on
Wszystkim, którzy znajâ normalnâ teorië grafów, ûyczë dobrej zabawy.
A tym, którzy jej nie znajâ radzë najpierw przeczytaê cokolwiek na
jej temat.
Serious mode off
Przystâpmy jednak do teorii...
def.1)
Graf jest to dostojnik w païstwie krzyûackim.
def.2)
Îaïcuch jest to przyrzâd do wykaïczania grafów. Posiada go kaûdy graf.
def.3)
Graf nieskoïczony to graf, który ûyje.
def.4)
Graf skoïczony to graf, który zostaî wykoïczony îaïcuchem przez innego
grafa, albo zginâî pod Grunwaldem.
TW.1)
Graf nieskoïczony zawiera sië w grafie skoïczonym.
DOWÓD: Ze wzglëdu na trywialnoôê pomijamy.
def.5)
Scieûka jest to droga, którâ porusza sië graf.
Lemat 1)
Kaûdy graf chodzi wîasnâ ôcieûkâ.
DOWÓD: Jeôli dwu dostojników wchodzi sobie w drogë, to prëdzej czy póúniej zostanie tylko jeden. Stanem stabilnym jest zatem: 1 graf - 1 ôcieûka.
TW.1)
Jeôli dwie scieûki sië przecinajâ, to na co najmniej jednej znajduje
sië graf skoïczony.
DOWÓD: Z lematu 1 wnioskujemy, ûe w razie spotkania dwu grafów przynajmniej jednemu z nich uda sië wykoïczyê laïcuchem przeciwnika. Z definicji 4 otrzymujemy, ûe graf jest skoïczony.
TW.2)
Istnieje taka dîugoôê îaïcucha, dla której prawdopodobieïstwo przejôcia
graf nieskoïczony -> graf skoïczony jest najmniejsze.
DOWÓD: Jeôli îaïcuch jest zbyt krótki, nie moûe speîniaê swoich zadaï, przez co graf-adwersarz ma przewage i îatwiej moûe spowodowaê przejôcie do stanu grafa skoïczonego. Z kolei zbyt dîugi îaïcuch jest nieporëczny, zatem równieû nie speînia swoich funkcji. Îaïcuch winien byê zatem dostatecznie dîugi, by byê skuteczny, a zarazem dostatecznie krótki, by byê porëczny.
def.6)
Dîugoscia optymalnâ îaïcucha nazywamy dîugoôê, przy której
graf nieskoïczony ma najmniejsze szanse staê sië grafem skonczonym.
def.7)
Siîa grafa jest to zdolnoôê grafa do posîugiwania sië îaïcuchem.
TW.3)
Optymalna dîugoôê îaïcucha dla kaûdego grafa moûe byê inna i jest
funkcjâ jego siîy.
DOWÓD: trywialny.
TW.4)
Zaleûnoôê dîugoôci optymalnej od siîy grafa jest sîabsza od liniowej.
DOWÓD: Maksymalna dîugoôê îaïcucha, którym moûe posîugiwaê sië graf roônie liniowo z siîâ grafa. Jednakûe silniejszy graf potrafi wyrzâdziê relatywnie wiekszâ szkodë nawet krótszym îaïcuchem. Jako dobrâ aproksymacjë przyjmuje sië zazwyczaj wzór:
TW.5)
a) Grafy o wiëkszej sile majâ mniejsze prawdopodobieïstwo stania sië
grafami skoïczonymi.
b) Istnieje pewna siîa grafa (uznawana za jednostkowâ), poniûej której
graf nie moûe byê w sposób trwaîy nieskoïczony.
DOWÓD: Sâ to proste wnioski z zaleûnosci podanej w dowodzie twierdzenia 4.