图论基础(一)

一、图论

        图论是数学的一个分支,它以图为研究对象。图论中的图是若干给定的点(顶点)以及连接两点的线(边)构成的图像,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。

        图几乎可以用来表现所有类型的结构或系统,从交通网络到通信网络,从下棋游戏到最优流程,从任务分配到人际交互网络,图都有广阔的用武之地。

表示出最基础的图:(这些与点的大小,边的粗细都无关,只表示点与点之间通过边的关系

 二、图的基础

        1.顶点(vertex)

         在图的应用中,每个顶点代表的含义均不相同,而是相互通过边相联系,因此将图中的每个顶点进行标号进行区分。

           ①.度数(degree)

                与该顶点相关联的总变数,一个图G的总度数 d(V) 等于总边数的两倍,当图的边有方向(有向图),一个顶点的度可分为出度(out-degree)入度(in-degree),出度是以该顶点为起点的边数,入度则是以该顶点为终点的边数。

                 ②阶数(order)

                  图中含有顶点的个数,即含有 n 个顶点,为 n 阶图

        2. 边(edge)

        顶点与顶点之间通过边联系,构成一个完整的图。

            ①权重(weight)

                边的权重(权值),即每条边都有与之对应的值。

                例如将两个顶点看成两个地点,边看成两个地点之间的距离。

三、图的分类

        综合以上,图可以分为以下几种

        1.有向图/无向图

               最基本的图通常被定义为“无向图”,与之对应的则被称为“有向图”。两者唯一的区别在于,有向图中的边是有方向性的。

        无向边:无固定方向的边,既可 x 到 y,又可以 y 到 x

        有向边:固定方向的边,即只能 x 到 y ,不能 y 到 x

         2.有权图/无权图

            有权图: 权值就是一条边的长度或代价。
            无权图: 不是边的权值为0,而是全都为1

        3.特殊的图——环

                在图论中,是一条只有第一个和最后一个顶点重复的非空路径。一个没有环的图被称作无环图,一个没有有向环的有向图被称做有向无环图。一个无环的连通图被称作树。

         4.连通图/连通分量

                在图G中,任意两个顶点之间都存在路径,则称G为连通图

上图虽然不是一个连通图(例 点8 与 点4 不连通),但它有两个连通子图,1234,56789,

        把一个图的最大连通子图称为它的连通分量。5,6,7,8,9顶点构成的子图就是该图的最大连通子图,也就是连通分量

连通分量特点:①子图

                         ②子图是连通的

                         ③子图含有最大的顶点数

对于连通图而言,最大连通分量就是其本身

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/265357.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

微信小程序引入Vant插件

Vant官网:Vant Weapp - 轻量、可靠的小程序 UI 组件库 先查看官网的版本 新建一个package.json页面,代码写上:(我先执行的npm安装没出package页面,所以先自己创建了一个才正常) {"dependencies"…

香港服务器选择指南(挑选香港服务器的几个标准)

​  随着全球化的加速和互联网的普及,跨境访问和外贸活动越来越频繁。在这个背景下,香港服务器作为一种国际化的基础设施,受到了广泛欢迎。本文将探讨企业在选择香港服务器时应关注的几个标准事项。 1.可靠性和正常运行时间 停机可能会给企…

华为ipv6 over ipv4 GRE隧道配置

思路: PC1访问PC2时,会先构造源ipv6为2001:1::2,目的IPV6为2001:2::2的ipv6报文,然后查看PC1的路由表,发送到R1,r1接收后,以目的IPV6地址2001:2::2查询IPV6路由表,出接口为tun0/0/0…

浅析ARMv8体系结构:原子操作

文章目录 概述LL/SC机制独占内存访问指令多字节独占内存访问指令 独占监视器经典自旋锁实现 LSE机制原子内存操作指令CAS指令交换指令 相关参考 概述 在编程中,当多个处理器或线程访问共享数据,并且至少有一个正在写入时,操作必须是原子的&a…

LabVIEW磁阻自动优化测量系统

LabVIEW磁阻自动优化测量系统 介绍了一种基于LabVIEW开发的磁阻自动优化测量系统,通过自动优化测试分辨率和高度模块化设计,大幅提升磁阻测试的效率和准确性。系统采用功率电源、电磁铁、高分辨率特斯拉计、步进电机转动器、精密电流源与精准电压表等硬…

Linux系统--nginx

1.Nginx(engine-x)由俄罗斯开发者Igor Sysoev开发,最初于2004年发布,主要用于解决C10K问题(即同时处理上万个并发连接)。其设计目标是实现高并发、低延迟以及高效利用硬件资源。Nginx不仅是一个静态内容服务器,还支持动…

安装使用zookeeper

先去官网下载zookeeper:Apache ZooKeeper 直接进入bin目录,使用powerShell打开。 输入: ./zkServer.cmd 命令,启动zookeeper。 zookeeper一般需要配合Dubbo一起使用,作为注册中心使用,可以参考另一篇博客&#xf…

【Ubuntu】解决Ubuntu 22.04开机显示器颜色(高对比度/反色)异常的问题

使用Ubuntu 22.04时强制关机了一下(make -j16把电脑搞崩了),开机后系统显示的颜色异常,类似高对比度或反色,如下图。看着很难受,字体也没办法辨认。还好之前遇到过类似的问题,应该是一个配置文件…

windows 11+docker desktop+grafana+influxDB+python写入

下载安装docker desktop 出现WSL相关的错误。WSL是一个linux内核的子系统,docker是基于linux内核的,所以运行docker需要WSL。 以管理员权限打开powershell,查看WSL状态 wsl --status 我遇到的错误是因为我关闭了windows的某些更新 执行上…

防火墙的内容安全

目录 1. 内容安全 1.1 IAE引擎 DPI---深度包检测技术 DFI---深度流检测技术 结论(优缺点): 1.2 入侵防御(检测)(IPS) IPS的优势: 入侵检测的方法: 入侵检测的流程 签名 查看预定义签名的内容 新建自定义签名 入侵防御的检测…

matlab绘制雷达图和二维FFT变换图

1、内容简介 略 49-可以交流、咨询、答疑 matlab绘制雷达图和二维FFT变换图 NMO组及NORMAL组 RNFL层、GCL层、IPL层、GCC层、ORL层做雷达图(共10张) 2、内容说明 略 NMO组及NORMAL组 RNFL层、GCL层、IPL层、GCC层、ORL层请分别做雷达图&#xff08…

在IDEA中创建vue hello-world项目

工作中最近在接触vue前端项目,记录一下从0搭建一个vue hello world项目的步骤 1、本地电脑安装配置node、npm D:\Project\vue\hello-world>node -v v14.21.3 D:\Project\vue\hello-world>npm -v 6.14.18 D:\Project\vue\hello-world> 2、设置npm国内淘…

【ArcGIS】重采样栅格像元匹配问题:不同空间分辨率栅格数据统一

重采样栅格像元匹配问题:不同空间分辨率栅格数据统一 原始数据数据1:GDP分布数据2.1:人口密度数据2.2:人口总数数据3:土地利用类型 数据处理操作1:将人口密度数据投影至GDP数据(栅格数据的投影变…

C# OpenCvSharp DNN Low Light image Enhancement

目录 介绍 效果 模型信息 项目 代码 下载 C# OpenCvSharp DNN Low Light image Enhancement 介绍 github地址:GitHub - zhenqifu/PairLIE 效果 模型信息 Model Properties ------------------------- ---------------------------------------------------…

深度学习环境安装

1.安装英伟达显卡驱动 首先需要到NAVIDIA官网去查自己的电脑是不是支持GPU运算。 网址是:CUDA GPUs | NVIDIA Developer。打开后的界面大致如下,只要里边有对应的型号就可以用GPU运算,并且每一款设备都列出来相关的计算能力(Comp…

ubuntu常见配置

ubuntu各个版本的安装过程大差小不差,可以参考,ubuntu20.04 其它版本换一下镜像版本即可 安装之后需要配置基本的环境,我的话大概就以下内容,后续可能有所删改 sudo apt-get update sudo apt-get install gcc sudo apt-get inst…

就业班 2401--2.26 Linux Day5--进程管理一

一、权限扩展 文件权限管理之: 隐藏权限防止root误删除 文件属性添加与查看 [rootlinux-server ~]# touch file1 file2 file3 1.查看文件属性 [rootlinux-server ~]# lsattr file1 file2 file3 ---------------- file1 ---------------- file2 ----------------…

mongoose httpserver浅析

文章目录 前言一、结构体及其功能二、函数MG_LOGmg_http_listenmg_mgr_poll question参考链接 前言 mongoose是一款基于C/C的网络库,可以实现TCP, UDP, HTTP, WebSocket, MQTT通讯。mongoose是的嵌入式网络程序更快、健壮,易于实现。 mongoose只有mong…

LeetCode 0938.二叉搜索树的范围和:深度优先搜索(可中序遍历)

【LetMeFly】938.二叉搜索树的范围和:深度优先搜索(可中序遍历) 力扣题目链接:https://leetcode.cn/problems/range-sum-of-bst/ 给定二叉搜索树的根结点 root,返回值位于范围 [low, high] 之间的所有结点的值的和。…

【踩坑】PyTorch中指定GPU不生效和GPU编号不一致问题

转载请注明出处:小锋学长生活大爆炸[xfxuezhang.cn] 指定GPU不生效问题 解释:就是使用os.environ["CUDA_VISIBLE_DEVICES"] "1"后,后面使用起来仍然是cuda0. 解决:在最开头就使用 import os os.environ[&…