Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
complete_graph [2014/02/08 14:14] nikolaj |
complete_graph [2014/03/21 11:11] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
===== Complete graph ===== | ===== Complete graph ===== | ||
==== Set ==== | ==== Set ==== | ||
- | | @#88DDEE: $V,E$ ... set | | + | | @#55CCEE: context | @#55CCEE: $V,E$ ... set | |
- | | @#FFBB00: $ \langle V,E,\psi\rangle \in \mathrm{it}(E,V) $ | | + | | @#FFBB00: definiendum | @#FFBB00: $ \langle V,E,\psi\rangle \in \mathrm{it}(E,V) $ | |
- | | @#55EE55: $ \langle V,E,\psi\rangle $ ... simple graph | | + | | @#55EE55: postulate | @#55EE55: $ \langle V,E,\psi\rangle $ ... simple graph | |
- | | @#FFFDDD: $ u,v \in V$ | | + | | @#FFFDDD: for all | @#FFFDDD: $ u,v \in V$ | |
- | | @#55EE55: $ u\neq v\implies \exists !(e\in E).\ \psi(e)=\{u,v\} $ | | + | | @#55EE55: postulate | @#55EE55: $ u\neq v\implies \exists !(e\in E).\ \psi(e)=\{u,v\} $ | |
==== Discussion ==== | ==== Discussion ==== | ||
Line 15: | Line 15: | ||
The axiom $\{u\}\notin\mathrm{im}(\psi)$ says that there are no loops on a single vertex. | The axiom $\{u\}\notin\mathrm{im}(\psi)$ says that there are no loops on a single vertex. | ||
+ | === Theorems === | ||
+ | When dealing with simple graphs, if you add another vertex to a graph with $n$ vertices, you can add $n$ new edges at best. So a complete graph with $n$ vertices has maximally $\sum_{k=1}^{n-1}k=\frac{1}{2}n(n-1)$ edges. | ||
=== Reference === | === Reference === | ||
Wikipedia: [[http://en.wikipedia.org/wiki/Complete_graph|Complete graph]] | Wikipedia: [[http://en.wikipedia.org/wiki/Complete_graph|Complete graph]] |