graph-checker/src/theorems/toughness.rs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

use crate::Graph;

pub fn theorem15(g: &Graph, toughness: f64, min_degree: f64) -> bool {
    let max_ind_cutset_size = g.max_independent_cutset().cardinality as f64;
    let third_of_size = g.size as f64 / 3.0;
    let tmp = if third_of_size > max_ind_cutset_size - 1.0 {
        third_of_size
    } else {
        max_ind_cutset_size - 1.0
    };

    return toughness >= 1.0 && min_degree >= tmp;
}

pub fn theorem25(g: &Graph, toughness: f64, min_degree: f64) -> bool {
    return min_degree > g.size as f64 / (toughness + 1.0) - 1.0;
}