Edge search in graphs using incidence tests [Elektronische Ressource] / vorgelegt von Tatjana Gerzen

Description

Edge Search in Graphs Using Incidence TestsVon der Fakult at fur Mathematik, Informatik und Naturwissenschaftender RWTH Aachen University zur Erlangung des akademischen Gradeseiner Doktorin der Naturwissenschaften genehmigte Dissertationvorgelegt vonDiplom-MathematikerinTatjana Gerzenaus Karaganda (Kazachstan)Berichter: Universit atsprofessor Dr. Eberhard TrieschHochschuldozent Dr. Hubert RanderathTag der mundlic hen Prufung: 23.09.2008Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek onlineverfugbar.DanksagungW ahrend meiner Promotionszeit haben mich viele Dozenten, Kollegen, Ver-wandte und Freunde begleitet. Einigen von ihnen bin ich zu besonderemDank verp ichtet.Prof. Dr. E. Triesch danke ich fur seine st andige Unterstutzung und dafur,dass er mein Interesse auf das spannende Thema der kombinatorischen Suchegelenkt hat.Priv.-Doz. Dr. B. Randerath danke ich fur seine stete Diskussions- und Hil-fsbereitschaft, die mich immer dann, wenn ich der Verzwei ung nahe war,davor gerettet haben.Ich bedanke mich herzlich bei Frau Volkmann, den Professoren und meinenArbeitskollegen fur die angenehme Arbeitsatmosph are, die anregenden Gespr ache,die hitzigen Diskussionen und naturlic h ganz besonders fur die vielen wohltuen-den Feierabende.Mein pers onlicher Dank gilt auch Torsten Korne el und Andreas Muhlic henfur das ub eraus geduldige und hilfreiche Korrekturlesen dieser Arbeit.An meine Freunde sage ich: Spasibo! Danke!

Sujets

• Mathematics

Informations

• Publié par: rheinisch-westfalischen_technischen_hochschule_-rwth-_aachen
• Publié le: 01 janvier 2008
• Nombre de lectures: 8
• Langue: Deutsch

Extrait

Edge Search in Graphs Using Incidence Tests

VonderFakulta¨tfu¨rMathematik,InformatikundNaturwissenschaften der RWTH Aachen University zur Erlangung des akademischen Grades einer Doktorin der Naturwissenschaften genehmigte Dissertation

vorgelegt von

Diplom-Mathematikerin

Tatjana Gerzen

aus Karaganda (Kazachstan)

Berichter:Universit¨atsprofessorDr.EberhardTriesch Hochschuldozent Dr. Hubert Randerath

Tagderm¨undlichenPru¨fung:23.09.2008

Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verf¨ugbar.

Danksagung

Wa¨hrendmeinerPromotionszeithabenmichvieleDozenten,Kollegen,Ver- wandte und Freunde begleitet. Einigen von ihnen bin ich zu besonderem Dank verpflichtet. Prof.Dr.E.Trieschdankeichf¨urseinest¨andigeUnterstu¨tzungunddafu¨r, dass er mein Interesse auf das spannende Thema der kombinatorischen Suche gelenkt hat. Priv.-Doz.Dr.B.Randerathdankeichf¨urseinesteteDiskussions-undHil- fsbereitschaft, die mich immer dann, wenn ich der Verzweiflung nahe war, davor gerettet haben. Ich bedanke mich herzlich bei Frau Volkmann, den Professoren und meinen Arbeitskollegenfu¨rdieangenehmeArbeitsatmosph¨are,dieanregendenGespr¨ache, diehitzigenDiskussionenundnatu¨rlichganzbesondersf¨urdievielenwohltuen- den Feierabende. Meinperso¨nlicherDankgiltauchTorstenKorneffelundAndreasMu¨hlichen furdas¨uberausgeduldigeundhilfreicheKorrekturlesendieserArbeit. ¨ An meine Freunde sage ich: Spasibo! Danke! Thanks! Obrigada! Gracias! Dziekuje! MeinletztesundganzbesondersgroßesDankesch¨onrichtetsichanmeine Eltern.Dankefu¨reureliebevolleundumsichtigeHilfeunddafu¨r,dassihr mirstetsdieM¨oglichkeitoffengelassenhabt,dieWeltmitmeineneigenen Augen zu sehen.

Aachen, Mai 2008

Tatjana Gerzen

Vorwort

Aberdasahnungsvolle,Jahrewa¨hrendeSuchen im Dunkeln und seiner gespannten Sehnsucht, seiner Abwechslung von Zuversicht und Ermattung und seinem endlichen Durchbrechen zur Klarheit, das kennt nur, wer es selber erlebt hat. Albert Einstein

Jeder von uns war schon ein mal auf der Suche. Auf der Suche nach einem verlorengegangenemSchl¨ussel,nacheinerverlegtenBrille,nachdembesten Borschtsch-Rezept, nach einer Wohnung oder einem Job. Wonach auch im- mermansuchenmag,indenmeistenF¨allenwillmanesschnellfinden.Denn die Suche nimmt Zeit in Anspruch, kostet Arbeit und Geld. Bei mancher Suche lohnt vielleicht der Aufwand nicht. Es ist also von großer Bedeutung, den Aufwand einer Suche zu berechnen, zu minimierenoderabzuscha¨tzen.Insofernistesnichtu¨berraschend,dasseine solche Aufgabe die Mathematiker im Allgemeinen und die Verfasserin dieser ArbeitimBesonderennichtgleichg¨ultiglassenkonnte. Wirben¨tiun¨achsteinallgemeinesModellf¨ureinenSuchprozessund o gen z ¨endannMthodenzurL¨osungkonkreterProblemeentwickeln.Um muss e besonderseinfacheunddennochallgemeingu¨ltigeMethodenzuerhalten,nimmt maninderkombinatorischenSucheh¨aufigan,dasssowohldieMengeder Suchoperationen (z.B. unter dem Bett nach der Brille schauen, jemand nach dem Weg fragen) als auch die Suchmenge, d.h. die Menge, in der wir nach einem Objekt suchen wollen, (z.B. die Menge der Straßen, die wir auf der SuchenacheinemWegvonderHaust¨urbiszurBu¨rotu¨rnehmenko¨nnen), alsauchdieMengederm¨oglichenAntwortendiskretsind.Wirsindimmer nur an Suchalgorithmen interessiert, die das gesuchte Objekt mit Sicherheit finden. Wirk¨onnenunseinenSuchprozessalseinSpielzwischenAliceunddem Weißen Kaninchen ∗ vorstellen. Alice sucht nach dem Zauberwort, welches ∗ Alice im Wunderland, Lewis Carroll

diemagischeT¨uro¨ffnet.SiehateinenKartonmitFrage-Kartenundeinen mit Wort-Karten, eine davon ist die Karte mit dem hoch begehrten Zauber- wort. Das Kaninchen hat einen Karton mit Antwort-Karten und kennt das Zauberwort. Alice stellt dem Kaninchen eine Frage aus dem Frage-Karten- Repertoire. Das Kaninchen antwortet mit einer Antwort-Karte, wobei es sichnatu¨rlichstetsandieWahrheithaltenmuss.MitdererhaltenenIn- formationw¨ahltAliceeinezweiteFrage-Karteundsoweiter,bissiedas Zauberworterh¨alt.EinAlgorithmusistdanneineFolgevonFragen,sodass dieentsprechendenAntwortenzumAuffindendesZauberwortesfu¨hren.Wir gehen davon aus, dass zu jeder Wort-Karte so eine Folge an Fragen vorhan- denist.Selbstversta¨ndlichistAlicesehrungeduldig,siew¨urdegernewissen, wie viele Fragen sie stellen muss, um an das Zauberwort zu kommen. Da wirdieAntwortennichtkennen,wirdesunsleiderunm¨oglichsein,Alicedie genaueAnzahldern¨otigenFragenzunennen. InderSuchtheorieistmandeshalbinteressiertanSchrankenf¨urdieSuch- dauerimschlimmstmo¨glichenFall.Wirnehmendaf¨urinunseremSpielan, dassesdasrichtigeZauberwortnichtgibt.UmdasSpielindieLa¨ngezu ziehen(undsoinderreizendenGesellschaftvonAlicem¨oglichstlangezuver- weilen),darfsichdasKaninchenw¨ahrenddesSpielsumentscheiden,welches Wort am Ende das Zauberwort wird. Allerdings muss am Ende des Spiels genau eine Wort-Karte zu all seinen Antworten passen. An dieser Stelle ko¨nnenwirAlicenursagen,dasesbeinWort-Karten undqAntwort-Karten mindestens log q n ∗∗ Fragen dauern wird. Gruppentests sind ein Spezialfall der kombinatorische Suche, der zum Beispiel in der Medizin seine Anwendung findet. Zum ersten Mal formulierte die Idee der Gruppentests Dorfman, geleitet von einem konkreten Problem, welches wa¨hrenddesZweitenWeltkriegesentstand.DamalsmusstemanMillionen von Soldaten auf Syphilis testen. Dorfman hatte die Idee, die Blutproben vonSoldatenzumischenumimFalleeinesnegativenErgebnissesm¨oglichst vieleSoldatenalsnichtinfiziertausschließenzuko¨nnen. Allgemein sucht man hier nachddefekten Objekten einer SuchmengeT. Zum testenwa¨hltmanTeilmengenderSuchmengeundu¨berpru¨ft,obmindestens eindefektesObjektinderTeilmengeliegt.Dieeinzigmo¨glichenAntworten sind “ja” und “nein . ” PeterCameronf¨uhrtinseinemFilm“Codes”(ausderReihePopularLec- tures der London Mathematical Society) vor, wie man mit 4 Fragen, die der Zuschauer mit “ja” oder “nein” beantwortet, die von dem Zuschauer ∗∗ Dies ist die informationstheoretische Schranke (C. E. Shannon)

gew¨ahlteZahlzwischen1und15erratenkann.Dasisteinsch¨onesBeispiel eines Gruppentests. Die Suchmenge besteht aus den Zahlen 1 bis 15, wobei nach genau einer Zahl gesucht wird. Und die Anzahl der Fragen ist sogar bestmo¨glich,dadieinformationstheoretischeSchrankeindiesemFallgenau  log 2  1 15  = 4 ist. IndenmeistenF¨allenwirdesunmo¨glichsein,dieseSchrankezuerreichen, zum Beispiel weil die Struktur der SuchmengeTes nicht erlauben wird, T In vielen Anwendungen muss man zu-mit jedem Test zu halbieren. demdieM¨achtigkeitderTestmenge,d.h.dieAnzahlderinjedemTest zu¨uberp¨ufendenObjekte,vonvornehereinbeschr¨anken.Indemoben beschriebenen Fall der Syphilis-Erkennung hat sich zum Beispiel heraus- gestellt,dassdieBluttestsunzuverla¨ssigwerden,sobaldmanmehrals9 Blutproben zusammen mischt. Es ist also interessant, nach der Anzahlc d p (T) derimschlimmstmo¨glichenFallno¨tigenTestszufrageninAbha¨ngigkeitvon der Anzahlpjnieid,etkejbOred¨rfuwtresnu¨ebprh¨ochsteedemTestn.de WirgebenimKapitel2.3scharfeobereunduntereSchrankenf¨urc pd (T) im Falld= 2. Betrachten wir den Falld Alice= 2 etwas genauer. sucht jetzt nach einem Paar von Wort-Karten. Sie packt jeweilspWort-Karten zusammen, fragt das Kaninchen, ob mindestens eine davon eine der zwei gesuchten ist und erh¨altalsAntwort“ja”oder“nein”.AbernichtalleWortpaareergeben einenSinn.Wiever¨andertsichdieAnzahlderFragen,wennAlicenurnach sinnvollen Wortkombinationen sucht? Genau diesem Problem wollen wir un- sere Aufmerksamkeit in dieser Arbeit widmen. Denkt man an diskrete Suche und Optimierung, so denkt man auch unweiger- lich an Graphentheorie. Man kann sich einen Graphen, wie ein Netzwerk vorstellen. Man hat Objekte, die wir Knoten des Graphen nennen wollen, und Verbindungen dazwischen, genannt Kanten. Wir bezeichnen die Menge der Kanten eines Graphen mitEnEisesteh-enbaucsSDa.iehcanehzru¨kren nverbindungistdieSuchenacheinerku¨rzestenKantenverbindungineinem Graphen. Die Suche nach einer fehlerhaften Verbindung in einem Telefonnet- zwerkgenausowiedasSuchennacheinemVerwandschaftsverh¨altniszwischen zwei Menschen entspricht der Suche nach einer Kante in einem Graphen. Dankder¨ubersichtlichenStrukturderGraphenwaresdenMathematikern mo¨glichindenletzten40JahrenenormvieleResultateu¨berGraphenzube- weisen. Um diese zu nutzen wollen wir versuchen, unser Problem der Suche nach zwei Wort-Karten als eine Suche in einem Graphen darzustellen. Stellen

wir uns die Wort-Karten als Knoten eines GraphenGvor und verbinden je zwei Karten, die ein sinnvolles Wortpaar ergeben, durch eine Kante. Wir suchen nun nach zwei Knoten inG, die durch eine Kante verbunden sind, d.h. nach einer unbekannten KanteeindeeseeUmdi.nleahw¨n,reeizfiitnediuzgitu wir TeilmengenXder Knotenmenge vonGigkeachtochsith¨etsn¨Mredpund stellen Fragen der Form: “Ist mindestens ein Knoten ausXein Endknoten voneInteresse gilt dabei der Anzahl der Fragen ?” Unserc p 2 (V) =c p (G), die imschlimmstmo¨glichenFallnotwendigsindumdiebeidenEndknotenvone zu finden. Bislang wusste man, dass im Falle, dasspnedreßgroggbitwhl¨aewleeib kann, mindestens log 2 |E|rFganenuhdo¨hctssenvieledlog 2 n(n−1)eFra- genimschlimmstmo¨glichenFallnotwendigsind.AuchderFallp= 1 ist genauestens untersucht worden. Details findet der Leser im ersten Kapitel dieser Arbeit. DaszweiteKapitelbesch¨aftigtsichmitdenSchrankenf¨urc p (G). Wir be- weisen eine untere Schranke und geben eine Vermutung an, wie die Schranke versch¨arftwerdenkann.Wirpr¨asentierenaußerdemeinescharfeobereSchranke f¨urc p (Gnu)psnehegdaullieezllvoenfddngitsa¨paehnerGnK n in,feen¨urd die allgemeine untere Schranke verbessert werden kann, sodass die Differenz zwischenderoberenundderunterenSchrankenmaximal3betra¨gt.Weiter verbessernwirf¨urgewissendieobereScnarh¨fekruc p (K n ). Im dritten Kapitel betrachten wir das Entscheidungsproblem, obc p (G)≤k f¨ureinegegebenenat¨urlicheZahlk stellen fest, dass das Problemgilt. Wir NP-vollsta¨ndigistf¨urallep. Das vierte Kapitel ist der Analyse der Greedy-Strategie gewidmet. Wir zeigen,daßdieFrage,obdieAnzahlderimschlimmstenFallben¨otigten Fragen kleiner oder gleichk,tosagdrnaNn-Povllst¨andigbleibtnman,iwsen diese spezielle Strategie benutzt. Allerdings kann man die Anzahl der Fragen, diebeieinemvollsta¨ndigenodereinembipartitenGraphbeno¨tigtwerden,in polynomiellerZeitbestimmen.Daru¨berhinausgebenwireineprobabilistis- che Analyse der Greedy-Schranke an. Imf¨unftenKapitelgehenwirausfu¨hrlichaufdenerfaßbarenFallp= 2 ein. Wir gebenc 2 (GxenessaliW.natkaseisewrgnkheapGrf)u¨eiserbewn einescharfeobereSchrankefu¨rdieAnzahlderKantenineinemGraphenin Abha¨ngigkeitvonc 2 (GhrScreteunfearchseniesuaradnetie)undl¨frunaek c 2 (GisiekterharaWirca).brenaufunterschieldcieheWsideeirGheapf¨n,ur dieGleichheitgiltundstellendieVermutungauf,dassfu¨rsolcheGraphen