图论导引-1

图论

1. 图G是由有限非空集合V及其二元子集E构成，其中V中的元素为顶点，E中的元素称为边。
2. V称为顶点集，E称为边集，记为G = （V，E）
3. 顶点称为点或者节点，边可以称为线，当两个图的V和E相等时，称为两个图相等。
4. 通常用平面上的图表来表示图，如V（G） = {P1，P2，P3，P4，……，Pn}；用E（G） = {{P1，P2}，{P1，P3}，……}
5. 在处理图的时候，将2元集{u，v}简写为uv（可交换）。
6. 如果uv是G的边，那么称u和v在G中是邻接的，并且u或v和uv是相互关联的。
7. G中的顶点数和边数称为该图的阶和边数。
8. 只有一个点的图称为平凡图，其余称为非平凡图，通常阶数用n表示，边数用m表示。若顶点有名字，称为标号图，没有名字则称为非标号图。
9. 有一个共同顶点的两条不同边称为邻接边。
10. 如果图H的V包含于图G的V，图H的E包含于图G的E，则称图H是图G的子图。与集合类似，也有真子图的说法。
11. 如果图G的一个子图和G有相同的顶点集（即边数为E(G)的真子集），称为G的生成子图。
12. 对于图G的一个子图F，如果子图中任意两个顶点u和v，只要uv∈E(G)，那么uv∈E（F），此时称F为G的诱导子图。
13.