现代图论 纲要

前言：寒假计划读这本Modern graph theory, Bollobas (GTM184)。每天会发一部分提纲。今天的部分是1.1.1节 definitions。有过图论基础的朋友应该基本都知道。

一. 基础:

1. 定义: （下汉语术语都由笔者捏造）

   1. 图(graph)、顶点(vertice)、边(edge)、连接(join)、相邻(neighbouring)、由..产生(be incident with)、子图(subgraph)、由...张成(spanned by)、阶(order)、大小(size)、同构(isomophic)、完全图(complete n-graph)、补图(complement of)、开（闭）邻域((closed) neighbourhood)、度(degree)、行走(walk)、路(path)、迹(trail)、圈(circle)、连通分量(complement)、最大\小度、最大连通子图、r分图(r-partite graph)、超图(hypergraph)、超图的生成图(incidence graph)、混合图(multigrpah)。

2. 几个术语的解释：

   hypergraph: a pair (V,E) such that V∩E=∅ and E is a subset of P(V)， the power set of V. 翻译下就是这图的边（超边）可以和任意个顶点连接。

   incidence graph of hypergraph: a bipartite graph with vertex classes V and E in which x∈V is joined to a hyperedge S∈E iff x∈S.把各个超边看作顶点和其包含的顶点连接形成的二分图。

   i.e. 

3. 定理（学过离散数学应该都知道）：

定理1. The edge set of a graph can be partiotioned into cycles iff every vertex has even degree.

定理2. Every graph of order n and size greater than ⌊n^2/4⌋ contains a triangle.(用柯西不等式证明）