Vi ger ett nytt bevis på resultatet, på grund av A. LaPaugh, att en graf kan vara optimalt "sökt" utan att rensa någon kant två gånger. O 19~~ Academic PWS, IIIC. Låt oss betrakta ett diagram som ett system av tunnlar som innehåller en (lycklig, osynlig, snabb) rymling. Vi vill fånga denna rymling genom att "söka" alla kanter av grafen, i en sekvens av diskreta steg, samtidigt som vi använder de minsta möjliga "vakter". Detta problem infördes av Breisch [2] och Parsons [6]. I den version av grafsökning som beaktas i [51 (som vi kallar kantsökning, med terminologi från [3]) ett söksteg består av att placera ett skydd på en vertex, eller ta bort ett skydd från en vertex, eller skjuta ett skydd längs en kant. Dessutom är en kant (u, v} rensas genom att skjuta ett skydd från u till u, medan avskärmning u från förorenade (det vill säga oklara) kanter med lämpligt placerade skydd (t.ex. genom att hålla ett annat skydd på u). Om det vid någon tidpunkt finns en stig från en förorenad kant och till en rensad kant e' som inte blockeras av vakter, blir e' omedelbart recontaminerad och måste rensas igen. Vårt mål är att nå ett tillstånd där alla kanter samtidigt rensas, så att det maximala antalet vakter som används vid varje steg minimeras. Varje strategi som uppnår detta resultat kallas optimal, och det optimala antalet vakter är kantsökning nummer grafen. LaPaugh [5] visade att det alltid finns en optimal strategi som är monoton (utan återkontaminering). En konsekvens av detta viktiga resultat är att det finns en optimal strategi som avslutas efter ett linjärt antal steg.
För alla diagram G finns det en optimal vinnande monoton (blandad sökning) strategi REF.
Monotonicity in Graph Searching
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}