Vi ger ett formellt och konstruktivt bevis i Coq/Ssreflekt av det kända resultatet att graferna på trädbredd två är exakt de som inte erkänner K4 som minderårig. Detta resultat är en milstolpe mot ett formellt bevis på det senaste resultatet att isomorfism av trädbredd-två grafer kan finit axiomatized. Beviset är baserat på en funktion som extraherar termer från K4-fria grafer på ett sådant sätt att tolkningen av en extraherad term ger en trädbredd-två graf isomorphic till den ursprungliga grafen. Bland de öppna problemen med trädbredd finns frågan om att finna finita axiomatisationer av isomorfism för grafer av en given trädbredd [5, sidan 118]. Denna fråga besvarades nyligen positivt för trädbredd två [14]: K 4 - fria grafer bildar den fria 2p-algebra, där 2p-algebras är algebraiska strukturer som kännetecknas av tolv ekvationella axiom. Beviset är ganska tekniskt; det bygger på en exakt analys av strukturen av K 4-fria grafer och innehåller den specifika formen av grafen mindre teorem för trädbredd två som vi presenterar här. Dessutom har ogiltiga bevis på närstående påståenden redan publicerats i litteraturen (se [14] ). Vårt långsiktiga mål är att formalisera ( †): inte bara kommer detta att ge oss försäkran om giltigheten av bevis i [14], det kommer också att möjliggöra utvecklingen av automation taktik för vissa algebraiska teorier (t.ex., 2p-algebra, allegorier [11] ). Den Coq-utveckling som åtföljer detta dokument [7] är en milstolpe för detta projekt. Oberoende av det ovan nämnda specifika målet, formaliserar grafen mindre teorem för trädbredd två kräver att vi utvecklar ett allmänt Coq-bibliotek för grafteori som också bör vara användbart i andra sammanhang. Detta bibliotek innehåller för närvarande grundläggande begrepp som stigar, träd, subgrafer, isomorphisms och även några mer avancerade sådana: minderåriga, träd sönderdelningar, och kontrollpunkter (en variant av skurna hörn). Vi var tvungna att designa det här biblioteket från grunden. I själva verket finns det mycket få formaliseringar av grafteori resultat i Coq, och ingen av dem var tillämpliga. Gonthiers formella bevis för Four-Color Theorem [12] är förvisso det mest avancerade, men det begränsar (genom design) till planar grafer så att det inte kan användas som utgångspunkt för grafteori i stort. På samma sätt använder Durfourd och Bertots studie av Delaunay triangulation [9] en bild av grafer baserade på hyperkartor inbäddade i ett plan. Det finns fler formaliseringar i andra interaktiva teorem bevis. Till exempel formaliserades plana grafer i Isabelle/HOL för Flyspeckprojektet [16]. Noschinski har nyligen utvecklat ett bibliotek för både enkla och multigrafer i Isabelle/HOL [17]. Chou utvecklade en stor del av oriktad grafteori i HOL [2]. Eulers teorem formaliserades i Mizar [15]. Så vitt vi vet formaliserades aldrig teorin om minderåriga och trädförruttnelser.
I ett nyligen utfört arbete REF som syftar till att formalisera grafen mindre teorem för trädbredd två Doczkal et al. utvecklade ett allmänt bibliotek för grafer med hjälp av Coq Proof Assistant.
A Formal Proof of the Minor-Exclusion Property for Treewidth-Two Graphs
{'venue': 'ITP', 'journal': None, 'mag_field_of_study': ['Computer Science']}