Content deleted Content added
cleanup, give more formal definition |
→Formal definition: wikilink for bijective |
||
Line 7:
Let ''G'' = (''U'' ∪ ''V'', ''E'') be a bipartite graph, i.e, the vertex set is ''U'' ∪ ''V'' where ''U'' ∩ ''V'' = ∅.
Let ''N''<sub>''G''</sub>(''v'') denote the neighborhood of a vertex ''v'' ∈ ''V''.
The graph ''G'' is '''convex''' over ''U'' if and only if there exists a [[bijective]] mapping, ''f'': ''U'' → { 1, 2, ..., |''U''| − 1, |''U|''}, such that for all ''v'' ∈ ''V'',
for any two vertices ''x'',''y'' ∈ ''N''<sub>''G''</sub>(''v'') ⊆ ''U'' there does not exist a ''z'' ∉ ''N''<sub>''G''</sub>(''v'') such that ''f''(''x'') < ''f''(''z'') < ''f''(''y'').
| |||