Abstract
Enlarging directed graphs to ensure that all nodes are contained in cycles. This research expands on previous research into a graph-matching problem, known as the ‘shoe-matching problem’, and the role of a graph-enlargement algorithm in finding this solution. Multiple new algorithms focusing on graph enlargement and the shoe-matching problem are presented with positive results overall.
Die vergroting van grafieke het voorheen neergekom op vergroting deur middel van sybyvoeging. Hierdie navorsing beskou die probleem vanuit ’n ander oogpunt, naamlik die vergroting van grafieke deur middel van nodusbyvoeging. Die vergroting van grafieke word toegepas om ’n passingsprobleem, in besonder die ‘skoenpassingsprobleem’, op te los.
In die navorsing word drie nuwe algoritmes vir grafiekvergroting voorgestel, naamlik matriksvergroting, subgrafiekvergroting en kostebesparende vergroting. Die algoritmes verbeter die effektiwiteit en doeltreffendheid van die bestaande algoritme wat deur Sanders (2013) voorgestel is.
Die kostebesparende algoritme is, afgesien van enkele wysigings, nou verwant aan die oorspronklike algoritme van Sanders (2013). Die algoritme is gemoeid met die minimalisering van unieke plekhouernodusse. Die unieke getal plekhouernodusse en die totale getal plekhouernodusse wat benodig word, kan verskil. Indien ’n plekhouernodus deel vorm van meer as een siklus, byvoorbeeld drie siklusse, moet die enkele unieke plekhouernodus drie keer aangeskaf word om te verseker dat alle siklusse bevredig word. Ons het in ons navorsing bevind dat die volgende metodes die getal unieke plekhouernodusse kan verminder:
- Geïsoleerde nodusse moenie aan groter grafiekstrukture gekoppel word nie, tensy dit die mees optimale aksie is. Oor die algemeen is dit meer koste-effektief om ’n plekhouernodus direk aan die geïsoleerde nodus te koppel.
- Brugnodusse moet sover moontlik vermy word. Met die oog hierop, moet komponente apart vergroot word.
- As spesifieke nodusse in veelvuldige siklusse herhaal word, kan die herhalings saamgepers word om te vermy dat dieselfde nodusse verskeie kere gekoop word.
Die subgrafiek-vergrotingsalgoritme isoleer alle siklusse indien die nodusse slegs een maal in die voorgenoemde siklusse voorkom. Met ander woorde, ’n stel siklusse word eenkant gesit en daar is geen nodusherhalings in die stel siklusse nie. Hierdie optimale keuse van siklusse vereis ’n kombinatoriese algoritme om al die beskikbare moontlikhede te evalueer. Die optimale stel siklusse word eenkant geplaas en as ‘voltooid’ gemerk. Die res van die grafiek konstrueer ’n subgrafiek van die oorspronklike, en word dan normaalweg deur die kostebesparingsalgoritme vergroot.
Die matriksvergrotingsalgoritme bied ’n nuwe en innoverende metode van grafiekvergroting. Die algoritme kan ook baie NP-volledige subprosesse oorslaan, wat tot ‘n hoë doeltreffendheid lei. Die algoritme herskryf die adjunksiematriks van die grafiek na ’n permutasiematriks om te verseker dat die grafiek slegs uit disjunkte siklusse bestaan. Die proses beskik oor die vermoë om groot grafieke (1000+ nodusse) binne sekondes op ’n moderne persoonlike rekenaar te vergroot.
Die doel van die navorsing was om nuwe en meer effektiewe algoritmes te ontwerp waarmee grafieke vergroot word. Daar is bevind dat die nuwe metodes twee tot drie keer meer doeltreffend is as Sanders (2013) se oorspronklike grafiek-vergrotingsalgoritme.
Literatuurverwysings
Sanders, I., 2013, ‘Cooperating to buy shoes: An application of picking cycles in directed graphs’, in Proceedings of the South African Institute of Computer Scientists and Information Technologists (Theme: ‘A Connected Society’), East London, pp. 8–16. http://dx.doi.org/10.1145/2513456.2517086
| 
Hide
Show all
Email this article (Login required)
Post a Comment (Login required)
