草庐IT

离散数学与组合数学-04图论上

IT从业者张某某 2023-09-04 原文

文章目录


本文为离散数据与组合数学电子科技大学王丽杰老师的课程笔记,详细视频参考
【电子科技大学】离散数学(上) 王丽杰
【电子科技大学】离散数学(下) 王丽杰
latex的离散数学写法参考: 离散数学与组合数学-01

离散数学公式
!符号 代码 含义
∧ \wedge \wedge 且
∨ \vee \vee 或
∩ \cap \cap 交
∪ \cup \cup 并
⊆ \subseteq \subseteq 子集
⊈ \nsubseteq \nsubseteq 不是子集
⊂ \subset \subset 真子集
⊄ \not\subset \not\subset 不是真子集
∈ \in \in 属于
∉ \not\in \not\in 不属于
↔ \leftrightarrow \leftrightarrow 等价
⇔ \Leftrightarrow \Leftrightarrow 等值
¬ \neg ¬ \neg或\lnot 非
R \mathbb{R} R \mathbb{R} 实数集
Z \mathbb{Z} Z \mathbb{Z} 整数集
∅ \varnothing \varnothing 空集
∀ \forall \forall 对任意的
∃ \exists \exists 存在
≥ \geq \geq大于等于
≤ \leq \leq 小于等于

下标的输入命令是: x 内容 x_{内容} x内容 x_{内容}
上标的输入命令式: x 2 x^2 x2 x^2
空格 \quad

R / R\mkern-10.5mu/ R/ R\mkern-10.5mu/ 数值越大,斜杆越往字母左侧移动

离散数学与组合数学-04图论上

4.1 图的引入

4.1.1 图的示例

图论发源于十八世纪, 最早主要研究一些游戏问题: 如哥尼斯堡七桥问题, 迷宫问题和博弈问题等. 计算机出现以后, 图论得到了长足的发展, 至今仍然活跃在科研和实际应用的第一线, 如现在受到普遍关注的云计算, 大数据应用和深度学习等.
图论所讨论的图 (Graph) 与人们通常所熟悉的图 (如圆、椭圆、函数图表等) 是很不相同的.图论中的图是指某类具体离散事物集合和该集合中的每对事物间以某种方式相联系的数学模型.


4.1.2 无序对和无序积

4.1.3 图的定义

4.2 图的表示

4.2.1 集合表示和图形表示

4.2.2 矩阵表示法

4.2.3 邻接点与邻接边

4.3 图的分类

4.3.1 按边的方向分类

4.3.2 按平行边分类


4.3.3 按权值分类



4.3.4 综合分类方法

4.4 图论基础-子图和补图

4.4.1 子图


4.4.2 完全图

4.4.3 补图



4.5 图论基础-握手定理

4.5.1 结点的度数




4.5.2 握手定理




4.5.3 图的度数序列

4.6 图论基础-图的重构

4.6.1 引言

4.6.2 图的同构定义



4.6.3 图同构的必要条件


4.7 图论基础-通路和回路

4.8 图论基础-可达性与最短通路

4.9 图论基础-无向图的连通性

4.10 图论基础-有向图的连通性

4.11 图论基础-认识树

有关离散数学与组合数学-04图论上的更多相关文章

  1. kvm虚拟机安装centos7基于ubuntu20.04系统 - 2

    需求:要创建虚拟机,就需要给他提供一个虚拟的磁盘,我们就在/opt目录下创建一个10G大小的raw格式的虚拟磁盘CentOS-7-x86_64.raw命令格式:qemu-imgcreate-f磁盘格式磁盘名称磁盘大小qemu-imgcreate-f磁盘格式-o?1.创建磁盘qemu-imgcreate-fraw/opt/CentOS-7-x86_64.raw10G执行效果#ls/opt/CentOS-7-x86_64.raw2.安装虚拟机使用virt-install命令,基于我们提供的系统镜像和虚拟磁盘来创建一个虚拟机,另外在创建虚拟机之前,提前打开vnc客户端,在创建虚拟机的时候,通过vnc

  2. ruby - 最多 n 的组合 - 2

    给定一个数组a,什么是实现其组合直到第n的最佳方法?例如:a=%i[abc]n=2#Expected=>[[],[:a],[:b],[:c],[:a,b],[:b,:c],[:c,:a]] 最佳答案 做如下:a=%w[abc]n=30.upto(n).flat_map{|i|a.combination(i).to_a}#=>[[],["a"],["b"],["c"],["a","b"],#["a","c"],["b","c"],["a","b","c"]] 关于ruby-最多n的组合,我

  3. ruby - Rails 组合多个 activerecord 关系 - 2

    我想合并多个事件记录关系例如,apple_companies=Company.where("namelike?","%apple%")banana_companies=Company.where("namelike?","%banana%")我想结合这两个关系。不是合并,合并是apple_companies.merge(banana_companies)=>Company.where("namelike?andnamelike?","%apple%","%banana%")我要Company.where("名字像?还是名字像?","%apple%","%banana%")之后,我会写代

  4. ruby - 在 Ubuntu 14.04 中使用 Curl 安装 RVM 时出错 - 2

    我试图在Ubuntu14.04中使用Curl安装RVM。我运行了以下命令:\curl-sSLhttps://get.rvm.io|bash-sstable出现如下错误:curl:(7)Failedtoconnecttoget.rvm.ioport80:Networkisunreachable非常感谢解决此问题的任何帮助。谢谢 最佳答案 在执行curl之前尝试这个:echoipv4>>~/.curlrc 关于ruby-在Ubuntu14.04中使用Curl安装RVM时出错,我们在Stack

  5. ruby - 如何在 ruby 中组合/排列? - 2

    我有一个熟悉的问题,看起来像是数学世界的排列/组合。如何通过ruby​​实现以下目标?badges="1-2-3"badge_cascade=[]badges.split("-").eachdo|b|badge_cascade["1","2","3"]ButIwantittobeis:=>["1","2","3","1-2","2-3","3-1","2-1","3-2","1-3","1-2-3","2-3-1","3-1-2"] 最佳答案 函数式方法:bs="1-2-3".split("-")strings=1.upto(bs.

  6. ruby - 我可以在 Ruby 中动态调用数学运算符吗? - 2

    ruby中有这样的东西吗?send(+,1,2)我想让这段代码看起来不那么冗余ifop=="+"returnarg1+arg2elsifop=="-"returnarg1-arg2elsifop=="*"returnarg1*arg2elsifop=="/"returnarg1/arg2 最佳答案 是的,只需像这样使用send(或者更好的是public_send):arg1.public_send(op,arg2)这是可行的,因为Ruby中的大多数运算符(包括+、-、*、/、andmore)只需调用方法。所以1+2与1.+(2)相同

  7. ruby - 更快的 n 选择 k 来组合数组 ruby - 2

    在尝试解决“网格上的路径”问题时,我编写了代码defpaths(n,k)p=(1..n+k).to_ap.combination(n).to_a.sizeend代码工作正常,例如ifn==8andk==2代码返回45,这是正确的路径数。但是,当使用较大的数字时,代码非常慢,我正在努力想出如何加快这个过程。 最佳答案 与其构建组合数组只是为了计算它,不如编写function定义组合的数量。我敢肯定还有包含此功能和许多其他组合函数的gem。请注意,我使用的是gemDistribution对于Math.factorial方法,但这是另一种

  8. ruby-on-rails - Ruby 哈希组合 - 2

    对于一个电子商务应用程序,我试图将选项的散列(每个选项都有一系列选择)转换为代表这些选择组合的散列数组。例如:#Input:{:color=>["blue","grey"],:size=>["s","m","l"]}#Output:[{:color=>"blue",:size=>"s"},{:color=>"blue",:size=>"m"},{:color=>"blue",:size=>"m"},{:color=>"grey",:size=>"s"},{:color=>"grey",:size=>"m"},{:color=>"grey",:size=>"m"}]Input内部可能有额

  9. ruby-on-rails - Ubuntu 14.04 Rails 丢失文件 - 2

    安装Rails时,一切都很好,但后来,我写道:rails-v和输出:/home/toshiba/.rvm/rubies/ruby-2.2.1/lib/ruby/site_ruby/2.2.0/rubygems/core_ext/kernel_require.rb:54:in`require':cannotloadsuchfile--rails/cli(LoadError)from/home/toshiba/.rvm/rubies/ruby-2.2.1/lib/ruby/site_ruby/2.2.0/rubygems/core_ext/kernel_require.rb:54:in`r

  10. Ubuntu20.04系统WineHQ7.0安装微信 - 2

    提供3种Ubuntu系统安装微信的方法,在Ubuntu20.04上验证都ok。1.WineHQ7.0安装微信:ubuntu20.04安装最新版微信--可以支持微信最新版,但是适配的不是特别好;比如WeChartOCR.exe报错。2.原生微信安装:linux系统下的微信安装(ubuntu20.04)--微信适配的最好,反应最快,但是微信版本只到2.1.1,版本太老,很多功能都没有。3.深度deepin-wine6安装微信:ubuntu20.04+系统deepin-wine6安装新版微信--综合比较好,当前个人使用此种方法1个月,微信版本3.4;没什么大问题,尚可。一、WineHQ7.0安装微信

随机推荐