Quellcodebibliothek Statistik Leitseite products/Sources/formale Sprachen/PVS/graphs/   (Beweissystem der NASA Version 6.0.9©)  Datei vom 28.9.2014 mit Größe 2 kB image not shown  

SSL tree_paths.pvs   Interaktion und
PortierbarkeitPVS

 
tree_paths[T: TYPE]: THEORY
BEGIN

   IMPORTING tree_circ[T], paths[T], path_circ[T], circuits[T], cycles[T]

   u,v: VAR T
 
   m,n: VAR nat
   G: VAR graph[T]
   p,q: VAR prewalk

   dual_paths?(G,(p:Path(G)),(q:Path(G))):bool = p /= q AND p(0)=q(0)
    AND p(length(p)-1)=q(length(q)-1)

   Dual_paths(G):TYPE = {((p:Path(G)),(q:Path(G))) | dual_paths?(G,p,q)}

   IMPORTING abstract_min


   min_dual_paths(G: Graph[T], r: Path(G), s: Path(G) | dual_paths?(G,r,s)): 
            Dual_paths(G) = min[[Path(G),Path(G)],
   (LAMBDA (r:Path(G),s:Path(G)): length(r)+length(s)),
   (LAMBDA (r:Path(G),s:Path(G)): dual_paths?(G,r,s))]


   is_min_dual?(G,(p:Path(G)),(q:Path(G))):bool = dual_paths?(G,p,q) 
                      AND FORALL (r:Path(G),s:Path(G)): dual_paths?(G,r,s) 
                            IMPLIES  length(r) + length(s) >= length(p)+length(q)

   min_dual_def: LEMMA FORALL (G: Graph[T], r: Path(G), s: Path(G)):
                          dual_paths?(G,r,s) IMPLIES
                          is_min_dual?(G,proj_1(min_dual_paths(G,r,s)),
                                         proj_2(min_dual_paths(G,r,s))) 
                      AND  
                          dual_paths?(G,proj_1(min_dual_paths(G,r,s)),
                                        proj_2(min_dual_paths(G,r,s)))


   min_dual_exists: LEMMA FORALL (G: Graph[T], r: Path(G), s: Path(G)):
         dual_paths?(G,r,s) IMPLIES EXISTS (p,q:Path(G)): is_min_dual?(G,p,q)

   dual_path_trunc: LEMMA  FORALL (G: Graph[T], p: Path(G), q: Path(G)): 
     dual_paths?(G,p,q) IMPLIES 
         length(p)>1 AND length(q)>1 AND path?[T](G, p ^ (0, length(p) - 2)) 
         AND path?[T](G, q ^ (0, length(q) - 2)) 
         AND path?[T](G, p ^ (1, length(p) - 1)) AND path?[T](G, q ^ (1, length(q) - 1))

   dual_path_length: LEMMA FORALL (G: Graph[T], p: Path(G), q: Path(G)): 
         dual_paths?(G,p,q) IMPLIES length(p)>2 OR length(q)>2

   min_dual_reduc: LEMMA  FORALL (G: Graph[T], p: Path(G), q: Path(G)): 
         is_min_dual?(G,p,q) IMPLIES p(1) /= q(1) AND p(length(p)-2) /= q(length(q)-2)


   min_dual_distin: LEMMA  FORALL (G: Graph[T], p: Path(G), q: Path(G)): 
              is_min_dual?(G,p,q) IMPLIES 
                         (FORALL (i,j:nat):i<length(p)-1 AND j<length(q)-1 AND p(i)=q(j) 
                                      IMPLIES (i=0 AND j=0))

   dual_cycle: LEMMA  FORALL (G: Graph[T], p: Path(G), q: Path(G)): 
                  dual_paths?(G,p,q) AND 
                  (FORALL (i,j:nat):i<length(p)-1 AND j<length(q)-1 AND p(i)=q(j) 
                                       IMPLIES (i=0 AND j=0)) 
                      IMPLIES cycle?(G,trunc1(p) o rev(q)) 

                                    
   tree_one_path: LEMMA  tree?(G) AND
                               path_from?(G,p,u,v) AND
                               path_from?(G,q,u,v) IMPLIES
                                    p=q


END tree_paths

62%


¤ Diese beiden folgenden Angebotsgruppen bietet das Unternehmen0.13Angebot  Wie Sie bei der Firma Beratungs- und Dienstleistungen beauftragen können  ¤

*Eine klare Vorstellung vom Zielzustand




Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.