diff options
Diffstat (limited to 'graph-checker/src/theorems/forbidden.rs')
| -rw-r--r-- | graph-checker/src/theorems/forbidden.rs | 201 |
1 files changed, 201 insertions, 0 deletions
diff --git a/graph-checker/src/theorems/forbidden.rs b/graph-checker/src/theorems/forbidden.rs index 615cdb1..8c70916 100644 --- a/graph-checker/src/theorems/forbidden.rs +++ b/graph-checker/src/theorems/forbidden.rs @@ -25,3 +25,204 @@ pub fn theorem3_1(g: &Graph) -> bool { return g.is_2_connected() && g.is_free_of(&forbidden); } + +pub fn theorem3_2(g: &Graph) -> bool { + let claw = Graph { + size: 4, + matrix: vec![ + vec![0, 1, 1, 1], + vec![1, 0, 0, 0], + vec![1, 0, 0, 0], + vec![1, 0, 0, 0], + ], + }; + + let forbidden = vec![claw]; + return g.size >= 3 + && g.is_connected() + && g.is_locally_connected() + && g.is_free_of(&forbidden); +} + +pub fn corollary3_5(g: &Graph) -> bool { + let claw = Graph { + size: 4, + matrix: vec![ + vec![0, 1, 1, 1], + vec![1, 0, 0, 0], + vec![1, 0, 0, 0], + vec![1, 0, 0, 0], + ], + }; + + let ig = Graph { + size: 4, + matrix: vec![ + vec![0, 1, 0, 0], + vec![1, 0, 1, 0], + vec![0, 1, 0, 1], + vec![0, 0, 1, 0], + ], + }; + + let ag = Graph { + size: 5, + matrix: vec![ + vec![0, 1, 1, 0, 0], + vec![1, 0, 0, 1, 0], + vec![1, 0, 0, 0, 1], + vec![0, 1, 0, 0, 0], + vec![0, 0, 1, 0, 0], + ], + }; + + let is_2 = g.is_2_connected(); + let claw_free = g.is_free_of(&vec![claw]); + return (is_2 && claw_free && g.is_free_of(&vec![ig])) + || (is_2 && claw_free && g.is_free_of(&vec![ag])); +} + +// 2003 Gould + +pub fn theorem85(g: &Graph) -> bool { + let claw = Graph { + size: 4, + matrix: vec![ + vec![0, 1, 1, 1], + vec![1, 0, 0, 0], + vec![1, 0, 0, 0], + vec![1, 0, 0, 0], + ], + }; + + let ng = Graph { + size: 6, + matrix: vec![ + vec![0, 1, 1, 1, 0, 0], + vec![1, 0, 1, 0, 0, 1], + vec![1, 1, 0, 0, 1, 0], + vec![1, 0, 0, 0, 0, 0], + vec![0, 0, 1, 0, 0, 0], + vec![0, 1, 0, 0, 0, 0], + ], + }; + + return g.is_2_connected() && g.is_free_of(&vec![claw, ng]); +} + +pub fn theorem86(g: &Graph) -> bool { + let claw = Graph { + size: 4, + matrix: vec![ + vec![0, 1, 1, 1], + vec![1, 0, 0, 0], + vec![1, 0, 0, 0], + vec![1, 0, 0, 0], + ], + }; + + let p6 = Graph { + size: 6, + matrix: vec![ + vec![0, 1, 0, 0, 0, 0], + vec![1, 0, 1, 0, 0, 0], + vec![0, 1, 0, 1, 0, 0], + vec![0, 0, 1, 0, 1, 0], + vec![0, 0, 0, 1, 0, 1], + vec![0, 0, 0, 0, 1, 0], + ], + }; + + return g.is_2_connected() && g.is_free_of(&vec![claw, p6]); +} + +pub fn theorem87(g: &Graph) -> bool { + let claw = Graph { + size: 4, + matrix: vec![ + vec![0, 1, 1, 1], + vec![1, 0, 0, 0], + vec![1, 0, 0, 0], + vec![1, 0, 0, 0], + ], + }; + + let z2 = Graph { + size: 5, + matrix: vec![ + vec![0, 1, 0, 0, 0], + vec![1, 0, 1, 0, 0], + vec![0, 1, 0, 1, 1], + vec![0, 0, 1, 0, 1], + vec![0, 0, 1, 1, 1], + ], + }; + + return g.is_2_connected() && g.is_free_of(&vec![claw, z2]); +} + +pub fn theorem88(g: &Graph) -> bool { + let claw = Graph { + size: 4, + matrix: vec![ + vec![0, 1, 1, 1], + vec![1, 0, 0, 0], + vec![1, 0, 0, 0], + vec![1, 0, 0, 0], + ], + }; + + let wg = Graph { + size: 6, + matrix: vec![ + vec![0, 1, 1, 0, 0, 0], + vec![1, 0, 1, 0, 1, 0], + vec![1, 1, 0, 1, 0, 0], + vec![0, 0, 1, 0, 0, 0], + vec![0, 1, 0, 0, 0, 1], + vec![0, 0, 0, 0, 1, 0], + ], + }; + + return g.is_2_connected() && g.is_free_of(&vec![claw, wg]); +} + +pub fn theorem96(g: &Graph) -> bool { + let claw = Graph { + size: 4, + matrix: vec![ + vec![0, 1, 1, 1], + vec![1, 0, 0, 0], + vec![1, 0, 0, 0], + vec![1, 0, 0, 0], + ], + }; + + let ng = Graph { + size: 6, + matrix: vec![ + vec![0, 1, 1, 1, 0, 0], + vec![1, 0, 1, 0, 0, 1], + vec![1, 1, 0, 0, 1, 0], + vec![1, 0, 0, 0, 0, 0], + vec![0, 0, 1, 0, 0, 0], + vec![0, 1, 0, 0, 0, 0], + ], + }; + + return g.is_3_connected() && g.is_free_of(&vec![claw, ng]); +} + +pub fn conjecture17(g: &Graph) -> bool { + let claw = Graph { + size: 4, + matrix: vec![ + vec![0, 1, 1, 1], + vec![1, 0, 0, 0], + vec![1, 0, 0, 0], + vec![1, 0, 0, 0], + ], + }; + + return g.is_4_connected() && g.is_free_of(&vec![claw]); +} |