Sep 6

图 graph

顶点 vertex

边 edge

顶点集 vertex set

边集 edge set

有序 ordered

顶点也可以称为 点 point 或 结点 node

边也可以称为 线 line

简单图 simple graph

相同的 equal

邻接的 adjacent

G的顶点数称为 阶 order

G的边数称为 边数 size

只有一个顶点的图称为 平凡图 trivial graph,这意味着 非平凡图 nontrivial graph 的阶至少是2.

标号图 labeled graph

非标号图 unlabeled graph

连接 joined

邻点 neighbor

关联的 incident

子图 subgraph

包含 contain

真子图 proper subgraph

生成子图 spanning subgraph

诱导子图 induced subgraph

链 walk

闭的 closed

开的 open

长度 length

长度为0的链称为 平凡链 trivial walk

迹 trail ,即边没有被多次经过的u-v链

若链中没有重复的顶点,那么它是一条 路 path

回路 circuit 是一个长至少为3的闭迹

除了第一个和最后一个顶点外,没有顶点重复的回路称为 圈 cycle

k圈 k-cycle 是一个长度为k的圈

连通的 connected

连通分支 component

距离 distance

测地线 geodesic

直径 diameter

完全的 complete

补图 complement

空图 empty graph

二部图 bipartite graph

部集 partite set


多重图与有向图

多重图 multigraph

平行边 parallel edge

环 loop

有向图 digraph 或 directed graph

有向边 directed edge 或 弧 arc

起点 start point

终点 end point

定向图 oriented graph

定向 orientation


参数 parameter

度 degree

邻域 neighborhood

孤立(顶)点 isolated vertex ,即度为0

端点 end vertex 或 叶 leaf ,即度为1

G的最小度 minimum degree

G的最大度 maximum degree

图论第一定理 G中所有顶点的度的和恰好为G边数的两倍

G一定是连通图的条件判断:1.如果一个n阶图G包含一个度为n-1的顶点


正则图:G的顶点具有相同的度

正则的 regular