Pokročilá Témata v Grafové Algoritmy

link: http://www.cs.tau.ac.il/~rshamir/atga/atga.html

Tento archiv obsahuje materiál na kurz “Pokročilá Témata v Grafové Algoritmy” © učil Ron Shamir oddělení informatiky Tel-Aviv university, na 10/91-2/92 (Podzim 92), 4-6/94 (Jaro 94) a 4-6/97 (Jaro 97). To byl jeden semestr absolvent kurzu otevřené také pro seniory, s jednou tři hodiny setkání každý týden.

Samozřejmě zdůraznil, algoritmické a strukturální aspekty “pěkné” graf rodiny, zejména perfektní grafy, interval grafy, chordální grafy a srovnatelnost grafy.
Na Podzim 92 kurz byl do značné míry založen na klasické knihy Martin C. Golumbic “Algoritmické Teorie Grafů a Perfektní Grafy’ (Academic Press, 1980), a v některých částech také na rukopis “Umění Kombinatorika”, Douglase B. Westa.
Na Jaře 94 a na Jaře 97 průběh měl podobný základ, ale zdůraznil, novější materiál, a udělal spoustu odkaz na aplikace v molekulární biologii. (Viz webové stránky Algoritmy pro Molekulární Biologii pro mnohem více na tyto aspekty.)

Materiál k dispozici:

Podrobný přehled kurzu .

na Jaře 97 (HTML)

Jarní 94 (ASCII)

Podzim 92 (ASCII)

na Jaře 1997 studijní materiály (neorganizované; některé odkazy byly aktualizovány a nějaký materiál je čitelný pouze na TAU prohlížeče. Omlouvám se.)

ovšem oficiální webová stránka

samozřejmě aktivní webovou stránku

Zákoníci Jara 94 přednášky
Rozhovory byly napsané studenty a upravil lektor. Kompletní soubor poznámek byl následně editovány a formátovány pomocí Sariel Har-Peled . Díky, Sariel !

Můžete buď ke stažení kompletní poznámky jako jeden soubor ve formátu postscript (150 stran), Nebo každá přednáška samostatně.

Kryt

Titulní stránka

Obsah

Seznam Postav

Přednáška č. 1: Úvod do Teorie Grafů

Základní Definice a Zkratky

Průsečík Grafů

Kruhového oblouku Grafy

Interval Grafy

Line grafy bipartitní grafy

Přednáška #2: Perfektní Grafy

Definice dokonalé graf

Některé Definice a Vlastnosti

Perfektní Grafu Věta

Přednáška #3: Perfektní a Zaměřil Grafy

Perfektní Grafy

$p$-Kritických Grafů

A Polyedrické Charakteristika Perfektní Grafy

Silný Perfektní Graf Dohad

Trojúhelníkový Grafy

Úvod

Charakterizuje Trojúhelníkový Grafy

Uznávajíce, Trojúhelníkový Grafy

Časová Složitost

Přednáška #4: Rozpoznávání Trojúhelníků, Grafy

Rozpoznávání Trojúhelníků, Grafy

Generování PEO

Testování Eliminační Schéma

  • Naivní Algoritmus
  • Efektivní Algoritmus
  • Příklad
  • Správnosti Algoritmu
  • Složitost Algoritmu

Trojúhelníkový Grafy jako Průsečík Grafů

Evoluční Stromy

Trojúhelníkový Grafy jako Průsečík Grafů

Přednáška #5: Trojúhelníkový Grafy Jsou Perfektní

Trojúhelníkový Grafy Jsou Perfektní

Dokázat Tuto Vlastnost

Další Výsledky

Výpočetní Minimální Vyplnit

Problém

Vyplnit je NP-Těžké

  • Řetěz Grafy
  • Optimální Lineární Uspořádání (OLA)
  • Řetěz Graf Dokončení (CGC)
  • výsledek pro Vyplnění

Problémy

Přednáška č. 6: Algoritmy pro triangulovaný grafy a srovnatelnost grafy

Nějaké Optimalizace Algoritmů na Trojúhelníkovém Grafy

Výpočet chromatické číslo a všechny maximální kliky

Hledání $\alpha $ a $k$

Srovnatelnost Grafy

Některé Definice

Důsledky Třídy

Trojúhelník Lemma

Dekompozice Grafů

Přednáška #7: Jedinečně Částečně lze objednat Grafy

Jednoznačně Částečně Lze Objednat Grafy

Charakterizace a Rozpoznávání Algoritmů

Přednáška #8: Nějaký zajímavý graf rodiny, vyznačuje průsečík

Úvod

Permutační grafy

$F$-Grafy

`Regulátory vzduchu strike”

Složení permutace diagramu.

Tolerance grafy

Interval grafy jako podmnožina tolerance grafy.

Ohraničené a neohraničené tolerance grafy.

Přednáška #9: Srovnatelnost Grafy

Srovnatelnost Graf Uznání

Složitost Srovnatelnost Graf Uznání

  • Realizace
  • Složitost Analýzy

Barvení a Jiných Problémů na Porovnatelnost Grafy

  • Srovnatelnost Grafy Jsou Ideální
  • Maximální Váha Kliky
  • Výpočet $\alpha (G)$

Rozměr Dílčích Objednávek

Přednáška #10: Srovnatelnost invarianty a Intervalové Grafy

Srovnatelnost invarianty

Interval grafy

Přednáška #11: Interval Grafy

Preference a Indiferenční

Uznávajíce intervalu grafy

  • kvadratický algoritmus 1
  • Lineární Algoritmus

Více o po sobě jdoucích 1 majetek

Přednáška #12: Temporální Uvažování

Temporální Uvažování a Interval algebry

Interval splnitelnost problémy

Interval sendvič problémy a je u našich dveří

Lineární algoritmus pro je u našich dveří($\Delta _1}$)

Pásma, Pathwidth a Správné Pathwidth