离散数学基础 |
您所在的位置：网站首页 › n阶自补图的边数 › 离散数学基础 |
离散数学基础
|
图是一种重要的结构，不是几何中的图形，而是表示客观世界中对象之间关系的一个数学抽象。研究图相关的理论成为图论。 一、无向图及有向图图的概念：用图表示对象之间的关系，其中对象表示为顶点，他们之间的联系表示为边多重集合：元素可以重复出现的集合。图用G=（V,E）表示，V是非空顶点集，E是边集，E的每条表都是V中某一对顶点间的连接。当顶点分别是u,v时，连接这连个顶点的边可以组成一个二元组（u，v），或。无序积：A&B={ (x,y)|x\in A \wedge y\in B }零图：G=（V,E）中，顶点总数记做|V|,变数记做|E|。如果边数较少，称为稀疏图。一条边也没有的图称为零图。仅有一个顶点的图称为平凡图，平凡图比为零图。无向图：G=,其中定点V是非空有穷集合，其元素称为顶点；边集E为V&V的多重子集，其元素称为无向边（不限定边的方向），简称边。有向图：D=。D的基图：用无向边替代邮箱边 性质：V(G),E(G),V(D),E(D):G和D的顶点集，边集n阶图：n个顶点的图零图：E= \oslash 平凡图：一阶零图空图：V= \oslash 顶点和边的关联关系设 e=(u,v)是无向图G=(V,E)的一条边，称u，v为e的端点，e与u(v)关联，若u \ne v,则称e与u(v)关联次数为1；若u=v,则称e为环，此时称e与u的关联次数为2,；若w不是e端点，则称e与w的关联此时为0，无边关联的顶点称作孤立点。顶点的度数：设G=为无向图，v \in V,v的度数（度）符号d(v)/deg(v):顶点v关联的边数称为该顶点的度数。若v有环，计算度数d(v)增加2； 出度和入度（有向图）设D=为有向图，v \in V.v的出度 d^{+}(v) :v作为边的始点次数之和v的入度 d^{—}(v) :v作为边的终点次数之和v的度数d(v):=d^{—}(v)+d^{+}(v)所有顶点的入度之和等于所有顶点的出度之和。图论定理-握手定理任意无向图和有向图的所有顶点度数之和都等于变数的2倍，并且有向图的所有顶点入度之和等于出度之和等于边数多重图和简单图在简单图中，如果有2条或2条以上的边关联同一对顶点，则称这些边为平行边，平行边的条数称为重数。含有平行边的图称为多重图机务平行边也无环的图称为简单图 图的同构设 G_1= ,G_2= 为两个无向图（有向图），若存在双射函数 f:V_1\rightarrow V_2 ,使得对于任意的 v_i,v_j\in V_1 ,(v_i,v_j)\in E_1(\in E_1) 当且仅当 (f(v_1),f(v_j))\in E_2(\in E_2) ,并且， (v_i,v_j)(G=,G^1= 是两个图若 V^1 \subseteq V,且 E^1 \subseteq E, 则称G^1为G的子图，G为G^1的母图，记做 G^1 \subseteq G 补图：设G=为n阶无向简单图，以V为顶点集，所有使G成为完全图 K_n 的添加边组成的集合为边集的图，称为G相对于 K_{n} 的补图，记做 \bar{G} 。下图互为补图自补图：G与G的补图同构，则称自补图。 正则图：无向图G=,如果每个顶点的度数都是k，则图G称作k-正则图二、通路、回路、图的连通性通路和回路：给定图G=(无向或有向)，G中顶点与边的交替序列 \Gamma=v_0e_1v_1e_2...e_lv_l 若 \forall i(1点割：设无向图G=为联通图，对任意的顶点w \in V,若删除w及与w相关联的所有边后，无向图不再联通，则w称为割点；点割集：设无向图G=为连通图，若存在点集 V_{1} \subset V ，当删除 V_{1} 中所有顶点及与V1顶点相关联的所有边后，图G不再是联通的；而删除了V1的任何真子集 V_{2} 及与V2中顶点先关的所有边后，所得的子图仍是连通图，则称V1是G的一个点割集设无向图G=为连通图，任意边e \in E,若删除e后无向图不再联通，则称e 为割边，也成为桥边割集：略设无向图G=， V^1 \subset V ,若 P(G-V_1)>P(G)且 \forall V_``` \subset V_`,p(G-V_```)=P(G), 则称V^1为G的点割集。若{v}为点割集，则v为割点（G-v:从G中删除v及关联的边）三、图的矩阵表示设无向图G=,V={ v_{1},v_{2},...,v_{n}, },E={ e_{1},e_{2},...,e_{m} },令 m_{ij} 为 v_{i}与e_{j} 的关联次数，称 (m_{ij})_{n*m} 为G的关联矩阵，记做M（G）。 设无环有向图D=,V={ v_1,v_2,...,v_n }, E={e_1,e_2,,,e_m} ,令  四、图的应用1.欧拉图：在联通图G中，经过G中每条边一次且紧一次的通路，称为欧拉通路或欧拉路；若欧拉通路为回路，则称为欧拉回路。具有欧拉通路的图称为欧拉图，含有欧拉通路但没有回路的图称为半欧拉图。（哥尼斯堡七桥） 无联通图G是欧拉图的充分必要条件是联通的无奇点。无联通图G是具有一条欧拉通路的充分必要条件是联通的恰好有2个奇点。有向图G，通过图中每条边一次且仅一次的一条单向通路（回路）称作单向欧拉通路（回路） 2.哈密顿图： 无向图G，若存在一条路L，经过图中每个顶点一次且仅一次，则L称为哈密顿图，简称H-路；若存在一条回路C，经过图中的每个顶点一次仅且一次，C称为哈密顿回路，H-回路。哈密顿回路的图称作哈密顿图。  若图G=具有哈密顿回路，则对于顶点集的每个非空子集S，均有W（G-S）设G是一个连通平面图，G的边将G所在平面划分成若干个区域，每个区域称为G的一个面，其中面积无限的区域称为无限面或外部面；面积有限的区域称为有限面或内部面。包围每个面的所有边组成的回路称为该面的边界，边界的长度称为该面的次数。若区域记做R，则次数可以做deg(R)l联通平面图G，面的次数之和等于其边数的两倍。设有一个连通平面图G，共有n个顶点和m条边，其平面表示中共有r个面，则n=m+r=2成立，此公式称为欧拉公式。如果两个图 G_{1}和G_{2} 同构，或经过反复插入或消去2度顶点后同构，则称G1与G2同胚一个图是平面，仅且仅当它不含有与K5同胚的子图；也不含有与K3同胚的子图-----库拉图斯定理
|
【本文地址】
今日新闻 |
推荐新闻 |