derkel píše:"Věta o čtyřech barvách zní:
Každý planární(rovinny) graf je dobře vrcholově obarvitelný nejvýše čtyřmi barvami...
Derkel: včera jsem se sem pak nedostal, sumarizace myšlenek (tj. přeber si to nějak sám
) z PM alias SZ a místy též poněkud trapný pokus vyvrátit dogma o matematické suchosti
Jen upozorňuju, že některá zde zmíněná grafová thémata jsem dvě léta neviděl - žádný teoretický zásek by se vyskytovat ale neměl.
Quest: Zlotřilý vyučující lže žákům
Při své toulce po Sigilu jsem narazil na Bezradného, který se svěřoval s podezřením, že byl úmyslně obelhán svým vyšší fraktorem z Bratrstva řádu. Pokud se mu nepodaří v prohlášení člena vyššího postavení najít chaos, kdo ví, co s ním bude...
A co on to teda říkal...
Každý planární(rovinny) graf je dobře vrcholově obarvitelný nejvýše čtyřmi barvami.
Důkaz: Nechť je na dobré vrcholové obarvení grafu G třeba alespoň 5 barev. Potom ovšem G obsahuje jako svůj podgraf K5. Dle Kuratowského věty však takový graf není planární.
Aneb důkaz, který se jeví jako správný, ale je založený na jedné zásadní mýlce. A to na té, že když se graf obarvuje pěti barvami, musí obsahovat K5. Což tak docela nemusí být vždycky pravda. Co teď, kudyma na to...?
...pomohou nám přece NPC...
v hlavních rolích:
- chromatické číslo alias X(G) - určuje, kolik minimálně barev je třeba na obarvení grafu G, ale zejména tím také určuje minimální počet nezávyslých podmnožin uzlů potřebných na pokrytí všech uzlů grafu G.
- klikovost alias w(G) - určuje nejvyšší n, pro něž lze v grafu G najít jeho podraf isomorfní Kn; jinými slovy určuje, jaký největší úplný podgraf lze v grafu najít
vedlejší role:
- nezávislá podmnožina uzlů - množina uzlů grafu, mezi nimiž vzájemně není hrana (jinými slovy uzly, které mezi sebou neincidují).
A tyto postavy tvrdí svorně jednu a tutéž větu:
"X(G) >= w(g)"
aneb chromatické číslo je větší nebo rovno klikovosti, aneb na graf mohu potřebovat k obarvení více barev, než jaká je velikost jeho úplného podgrafu, aneb když na graf potřebuji k obarvení k barev, úplný graf, který v něm najdu, může být klidně menší.
Hmm... na první pohled - pro rovnost to, zdá se, platí - úplný graf K5 je třeba obarvit pěti barvami a i jeho klikovost je pět.
A co pro tu ostrou nerovnost? Obě postavy opět říkají, že samozřejmě ano. Kupříkladu kružnice délky 5 s dalším vrcholem uprostřed, s nímž jsou spojeny všechny uzly. Sama taková kružnice už potřebuje 3 barvy, ačkoli obsahuje pouze K2, s vrcholem uprostřed pak 4 barvy, přestože obsahuje pouze K3.
Komu by dnes ale člověk věřil...
Neformální důkaz: Vezměme si X(G) < w(g). To nám říká, že graf má větší klikovost - má "větší" úplný podgraf, než kolik je jeho nezávislých podmnožin. Ale už třeba graf K5 ukazuje, že to nelze - v úplném grafu je každý uzel nezávislou podmnožinou. Abych jimi pokryl všechny uzly, musí jich být 5. Ale klikovost K5 je taky 5... Anebo si vezmu graf W6 z obrázku, klikovost má 3, ale já pro něj potřebuju 4 barvy... falíruje, falíruje to...
X(G) a w(g) tedy jejich větu můžeme bez obav věřit. X(G) >= w(G).
A co to znamená - když si řeknu, že pro graf potřebuji 5 (nebo více) barev k obarvení, n jakožto určení Kn může pěti (nebo jinému většímu číslu) rovno být, ale taky může být menší. Takže se tam používá něco, co ne vždy je pravda, a chce se tím potvrdit pravda všeobecná - a to přece nejde...
Quest splněn - dostáváme expy, zápočty, 5 bodů, co já vím co...
. Snad ještě jeden autobus přidají, ale docela pochybuji...
.
), a neboť u FTL si zřejmě myslí, že v zimě jezdí MHDčkem málo lidí, tak překopali do novýho roku jízdní řády, spoustu autobusů zrušili a zbytek přesunuli na naprosto nepochopitelný časy 
Teda vlastne SUX ak budete chodiť do práce s busom 
