Springen naar inhoud

Lastig probleem in gerichte grafen met ingraad = uitgraad


  • Log in om te kunnen reageren

#1

Erik Leppen

    Erik Leppen


  • >250 berichten
  • 367 berichten
  • Ervaren gebruiker

Geplaatst op 20 oktober 2007 - 16:31

Ik heb een moeilijk probleem. Stel ik heb een gerichte graaf, waarbij elke kant een zekere capaciteit heeft, dus een soort netwerk. Bovendien geldt voor elke knoop: de som van de capaciteiten van alle ingaande kanten is gelijk aan de som avn de capaciteiten van uitgaande kanten. Dus er is een stroming mogelijk waarbij alle kanten volledig vol zijn. Nu is het probleem: bepaal zo'n stroming. Dat wil zeggen: gegeven een knoop met n ingaande en n uitgaande pijlen, verbind elke ingaande pijl met een uitgaande, waarbij verschillende ingaande pijlen op verschillende uitgaande pijlen worden afgebeeld.

Nu wil ik de knoop als kruispunt van wegen voorstellen, dus niet een punt maar een schijf met een zeker inwendig gebied. Trek nu verbindingslijnen tussen de pijlen zoals boven beschreven, maar op een zodanige manier dat ze elkaar niet snijden. De gegevens: van elke kant is de capaciteit bekend, en de hoek waaronder die binnenkomt.

Ik heb van een aantal voorbeelden een plaatje gemaakt. Ik heb de volgende drie knopen. Geplaatste afbeelding
Elk ervan heeft zes ingaande pijlen en zes uitgaande pijlen. Bepaalde groepen pijlen vormen samen één kant, die heb ik evenwijdig getekend. Dus bijvoorbeeld, bij de linker knoop komt een kant binnen met capaciteit 5.
Nu kan ik handmatig bij elk voorbeeld een mogelijke oplossing tekenen. Dan valt op dat de oplossing niet uniek is.
Geplaatste afbeelding

Ik hoef maar één oplossing te vinden, geformuleerd als "de i-de pijl van kant e gaat naar de j-de pijl van kant f". Hoe vind ik zo'n algemene oplossing? Is daar een algoritme voor?

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 20 oktober 2007 - 18:50

Ergens op de knoop zitten een ingang en uitgang naast elkaar. Verbindt deze ingang en uitgang. Merk op dat deze verbinding de knoop in twee deelgebieden splitst waarvan er in een geen in/uitgangen zitten. Doe nu alsof de net verbonden in/uitgangen er niet zijn. Herhaal dit proces totdat je alle in/uitgangen verbonden hebt.

Was dit wat je zocht?

#3

Erik Leppen

    Erik Leppen


  • >250 berichten
  • 367 berichten
  • Ervaren gebruiker

Geplaatst op 20 oktober 2007 - 21:53

Hmm dat is eigenlijk een heel eenvoudig idee. Wat jij in feite doet is de informatie over welke pijlen "bij elkaar" horen (in dezelde kant zitten), weggooien en dus gewoon met allemaal losse pijlen werken. Wat ik dus zou moeten doen is eerst alle in- en uitkomende pijlen sorteren op hun hoek, je krijgt dan een "geordende rij modulo cyclische verwisseling" en daarin zit altijd ergens de deelrij "in, uit". Aangezien pijlen met een verschillende richting nooit bij dezelfde kant kunnen horen, kan ik nu de laatste pijl van de ene kant verbinden met de eerste van de volgende.

Ik denk dat dit wel tot iets gaat leiden. Bedankt! :D

Maar nu inprogrammeren...





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures