Question

离散数学(图论基础)

Answer 1

设 A, B 为任意集合, 称集合 A&B = {(a, b)|a ∈ A, b ∈ B} 为 A 与 B 的无序积,(a, b) 称为无序对.
与序偶不同, 对 ∀a, b,(a, b) = (b, a).

一个图 (Graph) 是一个序偶 < V, E >，记为 G =< V, E >，其中：V = {v1, v2, · · · , vn} 是有限非空集合，vi 称为结点 (node)，V 称为结点集。
E 是有限集合，称为边集。E 中的每个元素都有 V 中的结点对与之对应，称之为边 (edge)。

每条边都是无向边的图称为无向图(undirected graph)；每条边都是有向边的图称为有向图(directed graph)；有些边是无向边，而另一些边是有向边的图称为混合图(mixed graph)。(混合图转化为有向图)

赋权图(weighted graph)G 是一个三重组 < V, E, g > 或四重组 < V, E, f, g >，其中 V 是结点集合，E 是边的集合，f 是从 V 到非负实数集合的函数（即结点的权值函数），g 是从 E 到非负实数集合的函数（即边的权值函数）。相应的，边或结点均无权值的称为无权图

设有图 G =< V, E > 和图 G1 =< V1, E1 >.
若 V1 ⊆ V，E1 ⊆ E，则称 G1 是 G 的子图(subgraph)，记为 G1 ⊆ G.
若 G1 ⊆ G，且 G1 ̸= G(即 V1 ⊂ V 或 E1 ⊂ E)，则称 G1 是 G 的真子图(propersubgraph)，记为 G1 ⊂ G.
若 V1 = V，E1 ⊆ E，则称 G1 是 G 的生成子图(spanning subgraph).
设 V2 ⊆ V 且 V2 ̸= ∅，以 V2 为结点集，以两个端点均在 V2 中的边的全体为边集的 G 的子图，称为 V2 导出的 G 的子图，简称 V2 的导出子(induced subgraph)

设 G =< V, E > 为一个具有 n 个结点的无向简单图，如果 G 中任意两个结点间都有边相连，则称 G 为无向完全图，简称 G 为完全图，记为 Kn。
设 G =< V, E > 为一个具有 n 个结点的有向简单图，如果 G 中任意两个结点间都有两条方向相反的有向边相连，则称 G 为有向完全图，在不发生误解的情况下，也记为 Kn。

设 G =< V, E > 为简单图，G′ =< V, E1 > 为完全图，则称G1 =< V, E1 − E >为 G的补图(complement of graph)，记为G。