def.1) Graf jest to dostojnik w panstwie krzyzackim.
def.2) Lancuch jest to przyrzad do wykanczania grafow. Posiada go kazdy graf.
def.3) Graf nieskonczony to graf, ktory zyje.
def.4) Graf skonczony to graf, ktory zostal wykonczony lancuchem przez innego grafa, albo zginal pod Grunwaldem.
TW.1) Graf nieskonczony zawiera sie w grafie skonczonym. DOWOD: Ze wzgledu na trywialnosc pomijamy.
def.5) Sciezka jest to droga, ktora porusza sie graf.
Lemat 1) Kazdy graf chodzi wlasna sciezka. DOWOD: Jesli dwu dostojnikow wchodzi sobie w droge, to predzej czy pozniej zostanie tylko jeden. Stanem stabilnym jest zatem: 1 graf - 1 sciezka.
TW.1) Jesli dwie sciezki sie przecinaja, to na co najmniej jednej znajduje sie graf skonczony. DOWOD: Z lematu 1 wnioskujemy, ze w razie spotkania dwu grafow przynajmniej jednemu z nich uda sie wykonczyc lancuchem przeciwnika. Z definicji 4 otrzymujemy, ze graf jest skonczony.
TW.2) Istnieje taka dlugosc lancucha, dla ktorej prawdopodobienstwo przejscia graf nieskonczony -> graf skonczony jest najmniejsze. DOWOD: Jesli lancuch jest zbyt krotki, nie moze spelniac swoich zadan, przez co graf-adwersarz ma przewage i latwiej moze spowodowac przejscie do stanu grafa skonczonego. Z kolei zbyt dlugi lancuch jest nieporeczny, zatem rowniez nie spelnia swoich funkcji. Lancuch winien byc zatem dostatecznie dlugi, by byc skuteczny, a zarazem dostatecznie krotki, by byc poreczny.
def.6) Dlugoscia optymalna lancucha nazywamy dlugosc, przy ktorej graf nieskonczony ma najmniejsze szanse stac sie grafem skonczonym.
def.7) Sila grafa jest to zdolnosc grafa do poslugiwania sie lancuchem.
TW.3) Optymalna dlugosc lancucha dla kazdego grafa moze byc inna i jest funkcja jego sily. DOWOD: trywialny.
TW.4) Zaleznosc dlugosci optymalnej od sily grafa jest slabsza od liniowej. DOWOD: Maksymalna dlugosc lancucha, ktorym moze poslugiwac sie graf rosnie liniowo z sila grafa. Jednakze silniejszy graf potrafi wyrzadzic relatywnie wieksza szkode nawet krotszym lancuchem. Jako dobra aproksymacje przyjmuje sie zazwyczaj wzor: Lo = Lo0 * (Sg - 1/Sg)/2, gdzie Lo0=const, Sg - sila grafa.
TW.5) a) Grafy o wiekszej sile maja mniejsze prawdopodobienstwo stania sie grafami skonczonymi. b) Istnieje pewna sila grafa (uznawana za jednostkowa), ponizej ktorej graf nie moze byc w sposob trwaly nieskonczony. DOWOD: Sa to proste wnioski z zaleznosci podanej w dowodzie twierdzenia 4.
def.1)
Graf jest to dostojnik w panstwie krzyzackim.
def.2)
Lancuch jest to przyrzad do wykanczania grafow. Posiada go
kazdy graf.
def.3)
Graf nieskonczony to graf, ktory zyje.
def.4)
Graf skonczony to graf, ktory zostal wykonczony lancuchem
przez innego grafa, albo zginal pod Grunwaldem.
TW.1)
Graf nieskonczony zawiera sie w grafie skonczonym.
DOWOD: Ze wzgledu na trywialnosc pomijamy.
def.5)
Sciezka jest to droga, ktora porusza sie graf.
Lemat 1)
Kazdy graf chodzi wlasna sciezka.
DOWOD: Jesli dwu dostojnikow wchodzi sobie w droge, to predzej
czy pozniej zostanie tylko jeden. Stanem stabilnym jest zatem:
1 graf - 1 sciezka.
TW.1)
Jesli dwie sciezki sie przecinaja, to na co najmniej jednej
znajduje sie graf skonczony.
DOWOD: Z lematu 1 wnioskujemy, ze w razie spotkania dwu grafow
przynajmniej jednemu z nich uda sie wykonczyc lancuchem przeciwnika.
Z definicji 4 otrzymujemy, ze graf jest skonczony.
TW.2)
Istnieje taka dlugosc lancucha, dla ktorej prawdopodobienstwo
przejscia graf nieskonczony -> graf skonczony jest najmniejsze.
DOWOD: Jesli lancuch jest zbyt krotki, nie moze spelniac swoich
zadan, przez co graf-adwersarz ma przewage i latwiej moze spowodowac
przejscie do stanu grafa skonczonego. Z kolei zbyt dlugi lancuch
jest nieporeczny, zatem rowniez nie spelnia swoich funkcji. Lancuch
winien byc zatem dostatecznie dlugi, by byc skuteczny, a zarazem
dostatecznie krotki, by byc poreczny.
def.6)
Dlugoscia optymalna lancucha nazywamy dlugosc, przy ktorej
graf nieskonczony ma najmniejsze szanse stac sie grafem skonczonym.
def.7)
Sila grafa jest to zdolnosc grafa do poslugiwania sie
lancuchem.
TW.3)
Optymalna dlugosc lancucha dla kazdego grafa moze byc inna
i jest funkcja jego sily.
DOWOD: trywialny.
TW.4)
Zaleznosc dlugosci optymalnej od sily grafa jest slabsza od
liniowej.
DOWOD: Maksymalna dlugosc lancucha, ktorym moze poslugiwac sie
graf rosnie liniowo z sila grafa. Jednakze silniejszy graf potrafi
wyrzadzic relatywnie wieksza szkode nawet krotszym lancuchem.
Jako dobra aproksymacje przyjmuje sie zazwyczaj wzor:
Lo = Lo0 * (Sg - 1/Sg)/2,
gdzie Lo0=const, Sg - sila grafa.
TW.5)
a) Grafy o wiekszej sile maja mniejsze prawdopodobienstwo
stania sie grafami skonczonymi.
b) Istnieje pewna sila grafa (uznawana za jednostkowa),
ponizej ktorej graf nie moze byc w sposob trwaly nieskonczony.
DOWOD: Sa to proste wnioski z zaleznosci podanej w dowodzie
twierdzenia 4.