Malgrange algoritme
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 8. juli 2016; checks kræver 5 redigeringer .Malgrange-algoritmen er en metode til at opdele en graf i stærkt forbundne undergrafer .
Algoritme
Lad en graf gives , hvor er det sæt af hjørner, hvori, , og er det sæt af buer, der er beskrevet af tilstødende matrix , hvor . Partitioneringsalgoritmen er som følger:
- For et vilkårligt vertex finder vi direkte og omvendte transitive lukninger .
- Vi finder . Sættet af toppunkter i dette skæringspunkt udgør toppunkterne for en maksimalt stærkt forbundet subgraf .
- Træk subgrafen fra den originale graf :.
- Grafen tages som den originale graf, og mens trin 1, 2, 3 i algoritmen gentages.
Litteratur
- A. Kofman. Introduktion til anvendt kombinatorik. - M. : Nauka, 1975. - S. 166. - 480 s.
Links
- Tamara Volchenskaya, Vladimir Knyazkov, Kursus "Introduktion til grafteori", Foredrag 7: "Metoder til at opdele en graf i maksimalt stærkt forbundne undergrafer" // Intuit.ru , 2008
| Algoritmer på grafer | |
|---|---|
| Søg efter sæler | |
| Flowmaksimering | |
| Matchende | |
| Kommunikationsgrafer | |
| Andet |
|