当前位置: 首页 > news >正文

【离散数学·图论】(复习)

一、基本概念

1.一些基本术语:

2.点u,v邻接(或相邻): 边e称为关联顶点u和v,or e连接u和v;

3.G=(V,E)中,顶点v所有邻居的集合:N(v), 成为v的邻域。

4.度 : deg(v)

5.悬挂点:度为1的顶点;

6.孤立点:度为0的顶点。

二、几个定理and概念

1.握手定理:边数的2倍=度数。  (总度数一定为偶数

2.无向图有偶数个奇数度顶点。 (由1.) (定理2)

3.度:deg^{-}(v) ;   度:deg^{+}(v)

4.有向图,边数=入度=出度   (定理3)

5.完全图:K_{n}  , 每个顶点的度:n-1

6.圈图:C_{n}

7.轮图:W_{n}  顶点数:n+1,边数:2n

8.立方体图:Q_{n}   顶点数:2^n,边数: n*(2^(n-1))

9.二部图(二分图):用颜色判断

10.完全二部图 K_{m,n}

11.从旧图到新图: (子图,并图等)

12.加权图 : 边上带权重

三、图的表示

1.邻接表

2.邻接矩阵

3.关联矩阵:

当ej关联vi时 :1;or : 0;

四、其它概念

1.图的同构:

对于G1(V1,E1),G2(V2,E2) ,存在映上的从V1到V2 的函数f;

f性质:对所有a,b  a和b在G1里相邻<->a和b在G2里相邻。

2.通路:从u到v,  (边的序列)

            长度:通路中的数目

                      对于权重图,则为各边的权重之和。

   回路:若一条通路在相同的顶点开始和结束,且长度大于0,则它是一条回路。

   若通路或回路不重复的包含相同的边,那么它就是简单的

   各边全不同的:简单回路;

   各点全不同的:基本回路;

3.可达性:vi到vj从在通路(不管长度)。

4.无向图连通性:

连通图:每一对顶点间都有一条路径;

or : 不连通图;

5.连通分量:是G的连通子图,而不是G的其它连通子图的真子图。(即G的最大连通子图)

6.有向图连通性:

(1)强连通:对任意a,b  a到b有,b到a也有;

(2)弱连通:在有向图的基本无向图中是连通的;

7.计算顶点间的通路:用矩阵相乘。

五、欧拉回/通路  (可一笔画出)  (边不重复)

1.欧拉回路 充要: 所有顶点度数都为偶数;

2.欧拉通路 充要:有2个顶点度数为奇数,其它为偶数。

六、哈密顿回/通路 (点不重复)  (无充要条件)

1.哈回=>....  (性质)

   定理:

2....=>哈

定理:

3....=>哈回

(1)狄拉克定理:

(2)奥尔定理:

例:

答:m=n>=2;

七、平面图与着色:

1.欧拉公式:

设G是带e条边和v个顶点的连通平面简单图。设r是G的平面图表示中的面数,则 r=e-v+2。

2.图着色

简单图的着色:给每个顶点都指定一种颜色,使没有两个相邻的顶点颜色相同。

(平面图的着色数不超过4)

http://www.lryc.cn/news/385867.html

相关文章:

  • 【ONLYOFFICE震撼8.1】ONLYOFFICE8.1版本桌面编辑器测评
  • Shell 脚本编程保姆级教程(上)
  • 凸优化相关文章汇总
  • Java鲜花下单预约系统源码小程序源码
  • 网络变压器和RJ45接线的方法
  • Matlab/simulink三段式电流保护
  • OOXML入门学习
  • k8s集群node节点加入失败
  • layui+jsp项目中实现table单元格嵌入下拉选择框功能,下拉选择框可手动输入内容或选择默认值,修改后数据正常回显。
  • 2024年客户体验的几个预测
  • 【C++】动态内存管理new和delete
  • Java面向对象特性
  • odoo17 tree视图添加按钮
  • PreparedStatement 与Statement 的区别,以及为什么推荐使用 PreparedStatement ?
  • wsl ubuntu 安装Anaconda3步骤
  • Vue3响应式 ref全家桶
  • Mac(M1芯片)安装多个jdk,Mac卸载jdk
  • Warning message:package ‘ggplot2’ is not available (for R version 3.2.3)
  • Spring Boot 过滤器和拦截器详解
  • Eureka介绍与使用
  • JVM专题九:JVM分代知识点梳理
  • wireshark常用过滤命令
  • 「全新升级,性能更强大——ONLYOFFICE 桌面编辑器 8.1 深度评测」
  • 线程版服务器实现(pthread_server)
  • js异常处理方案
  • C++文件路径处理2 - 路径拼接路径解析
  • 数据结构5---矩阵和广义表
  • jquery使用infinitescroll无线滚动+自定义翻页
  • 【漏洞复现】锐捷统一上网行为管理与审计系统——远程命令执行漏洞
  • 通义灵码上线 Visual Studio 插件市场啦!