blob: 3d5d90ddfa2dec39bb32b16aaa823e4f7c4317e7 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
Require Import InterfGraphMapImp.
Require Import Graph_Facts.
Require Import FSets.
Require Import SetsFacts.
Require Import Edges.
Import Edge RegFacts Props RegRegProps.
(* Some properties about the interference adjacency
and the same about preference adjacency *)
(* x is not in its own interference neighborhood *)
Lemma not_in_interf_self : forall x g,
~VertexSet.In x (interference_adj x g).
Proof.
intros x g. rewrite in_interf. intro H.
elim (In_graph_edge_diff_ext _ _ H). auto.
Qed.
(* x is not in its own preference neighborhood *)
Lemma not_in_pref_self : forall x g,
~VertexSet.In x (preference_adj x g).
Proof.
intros x g. rewrite in_pref. intro H. destruct H.
elim (In_graph_edge_diff_ext _ _ H). auto.
Qed.
(* If x is an interference neighbor of y in g
then y is an interference neighbor of x in g *)
Lemma interf_adj_comm : forall x y g,
VertexSet.In x (interference_adj y g) -> VertexSet.In y (interference_adj x g).
Proof.
intros x y g H. rewrite in_interf. rewrite edge_comm. rewrite <-in_interf. auto.
Qed.
(* If x is a preference neighbor of y in g
then y is a preference neighbor of x in g *)
Lemma pref_adj_comm : forall x y g,
VertexSet.In x (preference_adj y g) -> VertexSet.In y (preference_adj x g).
Proof.
intros x y g H.
rewrite in_pref in H. destruct H. rewrite edge_comm in H.
rewrite in_pref. exists x0. assumption.
Qed.
(* If x is an interference neighbor of any vertex of g then x is in g *)
Lemma in_interf_in : forall x r g,
VertexSet.In x (interference_adj r g) -> In_graph x g.
Proof.
intros x r g H. rewrite in_interf in H.
apply (proj1 (In_graph_edge_in_ext _ _ H)).
Qed.
(* If x is a preferenec neighbor of any vertex then x is in g *)
Lemma in_pref_in : forall x r g,
VertexSet.In x (preference_adj r g) -> In_graph x g.
Proof.
intros x r g H. rewrite in_pref in H. destruct H.
apply (proj1 (In_graph_edge_in_ext _ _ H)).
Qed.
|
