Isomorfvrije generatie van gesigneerde grafen Promotor: Nico Van Cleemput ([email protected]) Een gesigneerde graaf bestaat uit een simpele graaf G(V, E) samen met een functie σ : E → {+, −}. Deze functie σ noemen we de signatuur van de gesigneerde graaf. Frank Harary voerde dit begrip in de jaren vijftig in om problemen in de sociale psychologie te modelleren. Voor een vlakke graaf bestaat er een verband tussen de kleurbaarheid van de graaf en het bestaan van een stroom (die nergens nul is) in de duale graaf. Voor grafen ingebed in nietorienteerbare oppervlakken bestaat er een gelijkaardig verband, maar ditmaal voor het bestaan van een bepaalde stroom in een gesigneerde versie van de duale graaf. Dit is de reden dat er interesse is in stromen in deze gesigneerde grafen. Een stroom in een gesigneerde graaf is hetzelfde als voor een simpele graaf, enkel krijgt elke boog nu twee pijlen en voor negatieve bogen zijn deze tegengesteld geori¨enteerd. De negatieve bronnen gedragen zich dus als een bron of als een afvoer. Bovendien is het bestaan van een stroom (die nergens nul is) in een gesigneerde graaf invariant onder het uitvoeren van een zogeheten switching. Dit is het wisselen van de tekens van alle bogen incident met een bepaalde top. Voor simpele grafen is er het bekende vermoeden van Tutte dat elke graaf een stroom heeft die nergens nul is en maximale waarde 5 heeft. Voor gesigneerde grafen bestaat er een gelijkaardig vermoeden dat de maximale waarde 6 voldoende is. Er zijn echter slechts twee grafen en ´e´en oneindige familie van grafen gekend die echt 6 nodig hebben. Deze grafen zijn hieronder getekend en de negatieve bogen worden weergegeven in het rood. Elk van deze grafen heeft ook verschillende signaturen die stromen hebben met kleinere maximale waarden. Het doel van deze thesis is om een algoritme te ontwikkelen en te implementeren om gesigneerde grafen te genereren zonder isomorfe exemplaren onder de switching-isomorfie. Vervolgens kan dit algoritme ook gebruikt worden om te zoeken naar gesigneerde grafen die een stroom hebben met maximale waarde 6 en niet af te leiden zijn uit een van de bovenstaande voorbeelden. Voor kleine grafen zijn de aantallen van gesigneerde grafen reeds gekend op basis van een programma dat geen rekening houdt met switching-isomorfie.
© Copyright 2024 ExpyDoc
