Differences
This shows you the differences between two versions of the page.
|
k-partite_graph [2014/02/11 00:53] nikolaj |
k-partite_graph [2014/03/21 11:11] |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | ===== k-partite graph ===== | ||
| - | ==== Set ==== | ||
| - | | @#88DDEE: $k\in\mathrm N$ | | ||
| - | | @#88DDEE: $V$ ... set | | ||
| - | | @#FFBB00: $\langle V,E\rangle \in \mathrm{it}(E,V) $ | | ||
| - | |||
| - | | @#AAFFAA: $ \langle V,E\rangle $ ... undirected graph | | ||
| - | |||
| - | | @#DDDDDD: $ i,j\in\{1,\dots,k\} $ | | ||
| - | | @#DDDDDD: $ X_1,\dots,X_k\subset V $ | | ||
| - | | @#DDDDDD: $ \bigcup_i X_i=V $ | | ||
| - | | @#DDDDDD: $ \forall i,j.\ X_i\cap X_j=\emptyset $ | | ||
| - | | @#DDDDDD: $ v,w\in V $ | | ||
| - | |||
| - | | @#55EE55: $\exists X_1,\dots,X_k.\ \forall u,v.\ \{u,v\}\in E\implies \forall i.\ \neg(v\in X_i\land w\in X_i) $ | | ||
| - | |||
| - | ==== Discussion ==== | ||
| - | The $X_i$ are the partitions of the graph and the condition says that there can be no edge within an $X_i$, i.e. there are only connection from one partition to another. One can also few the partitions as different coloring of their vertices. | ||
| - | === Theorems === | ||
| - | From any $v\in X_i$, there can be edges to only the other partitions, i.e. to at most $|V|-|X_i|$ different other vertices. If we sum up the edges for all partitions and divide the double-counting out, we find that for an $k$-partite graph | ||
| - | |||
| - | $|E|\le \frac{1}{2}\sum_{i=1}^k |X_i|\cdot (|V|-|X_i|)$ | ||
| - | ==== Parents ==== | ||
| - | === Subset of === | ||
| - | [[Undirected graph]] | ||
