前言：寒假計(jì)劃讀這本Modern graph theory, Bollobas (GTM184)。每天會發(fā)一部分提綱。今天的部分是1.1.1節(jié) definitions。有過圖論基礎(chǔ)的朋友應(yīng)該基本都知道。

一. 基礎(chǔ):

1. 定義: （下漢語術(shù)語都由筆者捏造）

   1. 圖(graph)、頂點(diǎn)(vertice)、邊(edge)、連接(join)、相鄰(neighbouring)、由..產(chǎn)生(be incident with)、子圖(subgraph)、由...張成(spanned by)、階(order)、大小(size)、同構(gòu)(isomophic)、完全圖(complete n-graph)、補(bǔ)圖(complement of)、開（閉）鄰域((closed) neighbourhood)、度(degree)、行走(walk)、路(path)、跡(trail)、圈(circle)、連通分量(complement)、最大\小度、最大連通子圖、r分圖(r-partite graph)、超圖(hypergraph)、超圖的生成圖(incidence graph)、混合圖(multigrpah)。

2. 幾個(gè)術(shù)語的解釋：

   hypergraph: a pair (V,E) such that V∩E=? and E is a subset of P(V)， the power set of V. 翻譯下就是這圖的邊（超邊）可以和任意個(gè)頂點(diǎn)連接。

   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.把各個(gè)超邊看作頂點(diǎn)和其包含的頂點(diǎn)連接形成的二分圖。

   i.e.?

3. 定理（學(xué)過離散數(shù)學(xué)應(yīng)該都知道）：

定理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.(用柯西不等式證明）