图论(一)之概念介绍与图形#matlab

图论(一)之概念介绍与图形目录

前言

一、图论介绍

二、基本概念 

2.1图的概念

2.2图形分类

2.3邻接矩阵

 2.3.1无向图

2.3.2有向图

2.3.3有向赋权图

2.4出度(Outdegree)

2.5入度(Indegree)

3.四种图论图形的matlab代码

4.运行结果

5.图论应用

6.算法

总结


前言

        图论——这一专注于点和线之间关系的学科,如同一条独特的脉络,将无数看似孤立的领域紧密地连接在一起。


一、图论介绍

        从数学建模角度来看,图论(Graph Theory)是数学的一个分支,主要研究由若干给定的点(通常称为顶点或节点)以及连接这些点的线(通常称为边)所构成的图形。这种图形通常用来描述某些事物之间的某种特定关系,其中点代表事物,边表示事物之间具有的关系。

二、基本概念 

2.1图的概念

        图G通常表示为二元组(V(G),E(G))。公式(1)是非空有限集,称为顶点集,其中元素称为图G的顶点。顶点(或节点、点)是图中的基本元素,用来表示不同的对象、事件或位置。

V(G)=\{\nu_1,\nu_2,\cdots,\nu_\nu\},公式(1)

        公式(2)是顶点集V(G)中的无序(无向图)有序(有向图)的两个元素组合组成的集合,即称为边集,其中元素称为。边是连接两个顶点的线,表示顶点之间的关系或连接。边可以是有向的(单向关系),也可以是无向的(双向关系)。

E(G)=\{e_1,e_2,\cdots,e_n\}公式(2)

        赋权图:若图G=(V(G),E(G))的每一条边e都赋以一个实数w(e),称w(e)为边e的,G连同边上的权称为赋权图。

2.2图形分类

        所有图论里的图都可以根据是否有向和是否加权分类。

2.3邻接矩阵

       

图1 四种图论基本图

 2.3.1无向图

      

根据上图1中的无权无向图可以得出其邻接矩阵为:

2.3.2有向图

根据上图1中的无权有向图可以得出其邻接矩阵为:

2.3.3有向赋权图

根据上图1中的有权有向图可以得出其邻接矩阵为:

2.4出度(Outdegree)

        定义:由某个顶点指出的边的个数称为该顶点的出度;解释:在有向图中,一个顶点的出度表示从这个顶点出发的边的数量;换句话说,这些边都是以该顶点为“尾”(tail),指向其他顶点作为“头”(head)。

示例:在图3中,顶点D指向顶点A和顶点C,那么顶点D的出度就是2。

2.5入度(Indegree)

        定义:指向某个顶点的边的个数称为该顶点的入度;解释:在有向图中,一个顶点的入度表示指向这个顶点的边的数量;这些边都是以其他顶点为“尾”,以该顶点为“头”。

3.四种图论图形的matlab代码

clc; clear; 
%% 1. 创建无权的有向图和无向图 
V = {'A', 'B', 'C', 'D'}; 
E = {'A' 'B'; 'B' 'C'; 'C' 'D'; 'D' ,'A'}; 
% 1.1 创建无权有向图 
G_directed = digraph(E(:,1), E(:,2)); 
% 绘制图形 
figure; % 只在这里调用 figure,以创建一个新的图形窗口 
subplot(2,2,1); 
plot(G_directed, 'Layout', 'circle', 'NodeColor', [0.5294 0.8078 0.9804], ... 
'MarkerSize', 10, 'EdgeColor', 'black', 'ArrowSize', 10); 
title('无权有向图'); 
% 获取有向图的邻接矩阵 
adjacency_directed = adjacency(G_directed); 
disp('无权有向图的邻接矩阵:'); 
disp(adjacency_directed);
% 1.2 创建无权无向图 
E = {'A' 'B'; 'B' 'C'; 'C' 'D'; 'D' ,'A'}; 
G_undirected = graph(E(:,1), E(:,2)); 
subplot(2,2,2); 
plot(G_undirected, 'Layout', 'circle', 'NodeColor', [0.5294 0.8078 0.9804], ... 
'MarkerSize', 10, 'EdgeColor', 'black'); 
title('无权无向图'); 
% 获取无向图的邻接矩阵 
adjacency_undirected = adjacency(G_undirected); 
disp('无权无向图的邻接矩阵:'); 
disp(adjacency_undirected);
%% 2. 创建加权的有向和无向图 
weights = [1, 2, 3, 4,5]; % 边的权重 
% 2.1 创建有权有向图 
E = {'A', 'B'; 'B', 'C'; 'C', 'D'; 'D', 'A';'D','C'}; 
G_weighted_directed = digraph(E(:,1), E(:,2), weights); 
subplot(2,2,3); 
plot(G_weighted_directed, 'Layout', 'circle', 'NodeColor', [0.5294 0.8078 0.9804], ... 
'MarkerSize', 10, 'EdgeColor', 'black', 'ArrowSize', 10, 'EdgeLabel', weights); 
title('加权有向图'); 
% 初始化邻接矩阵(全无穷大) 
num_nodes = numel(V); 
adjacency_matrix_weighted_directed = inf(num_nodes, num_nodes); 
% 将对角线元素设置为0(节点到自身的权重为0) 
% 因为这里我们不需要考虑节点到自身的边(通常默认为0或不考虑),所以这步可以省略 
% 但为了保持一致性,我们还是设置它为0 
adjacency_matrix_weighted_directed(logical(eye(num_nodes))) = 0; 
% 填充邻接矩阵的权重 
for i = 1:length(E) 
source_index = find(strcmp(V, E{i, 1}), 1); % 找到源节点在V中的索引 
target_index = find(strcmp(V, E{i, 2}), 1); % 找到目标节点在V中的索引 
adjacency_matrix_weighted_directed(source_index, target_index) = weights(i); 
end 
% 显示邻接矩阵(可选) 
disp('有权有向图的邻接矩阵(权重表示,无边为无穷大):'); 
disp(adjacency_matrix_weighted_directed);
% 2.2 创建有权无向图 
E = {'A', 'B'; 'B', 'C'; 'C', 'D'; 'D', 'A';'D','C'}; 
G_weighted_undirected = graph(E(:,1), E(:,2), weights); 
subplot(2,2,4); 
plot(G_weighted_undirected, 'Layout', 'circle', 'NodeColor', [0.5294 0.8078 0.9804], ... 
'MarkerSize', 10, 'EdgeColor', 'black', 'EdgeLabel', weights); 
title('加权无向图');

4.运行结果

5.图论应用

        图论的应用范围非常广泛,涉及电信网络、电力网络、交通运输、计算机科学、控制论、人工智能、社会网络分析等多个领域。图论中的算法和理论在解决诸如最短路径问题、最小生成树问题、网络流问题等实际问题中发挥着重要作用。

6.算法

        图论算法包括深度优先搜索(DFS)、广度优先搜索(BFS)、Dijkstra算法(用于求解最短路径问题)、Prim算法和Kruskal算法(用于求解最小生成树问题)等。这些算法在图论的理论研究和实际应用中都具有重要意义。


总结

        综上所述,图论是一门研究图及其相关性质的数学分支,具有广泛的应用背景和重要的理论价值。

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

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

相关文章

联想电脑 调节屏幕亮度不起使用,按F5,F6,屏幕上的hotkeys进度条是在改变,但是屏幕没有一些作用的处理方法

1、查看驱动是否正常 Win键X ,设备管理器 发现似乎挺正常的。 查看原厂驱动:联想电脑管家 这样看来,驱动是没有问题了。 2、看看设置电池模式 其实还是这个电池模式的问题导致。 如果处于养护模式的话,充电只在75%~80%&#x…

【Numpy】一文向您详细介绍 np.round()

【Numpy】一文向您详细介绍 np.round() 下滑即可查看博客内容 🌈 欢迎莅临我的个人主页 👈这里是我静心耕耘深度学习领域、真诚分享知识与智慧的小天地!🎇 🎓 博主简介:985高校的普通本硕,…

【大数据】计算引擎:Spark核心概念

目录 前言 1.什么是Spark 2.核心概念 2.1.Spark如何拉高计算性能 2.2.RDD 2.3.Stage 3.运行流程 前言 本文是作者大数据系列中的一文,专栏地址: https://blog.csdn.net/joker_zjn/category_12631789.html?spm1001.2014.3001.5482 该系列会成体…

【SpringCloud学习笔记】RabbitMQ(上)

1. RabbitMQ简介 官网地址:https://www.rabbitmq.com/ 2. 安装方式 安装前置准备: 此处基于Linux平台 Docker进行安装,前置准备如下: Linux云服务器 / 虚拟机Docker环境 安装命令: docker run \-e RABBITMQ_DEFAU…

TCP与UDP案例

udp不会做拆分整合什么的 多大就是多大

【日记】第一次养植物,没什么经验……(781 字)

正文 前两天梦见灵送的几盆植物全都死掉了。梦里好伤心。醒来与她说这件事,她宽慰我说,梦都是反着的,肯定能活得很好的。于是忽然记起昨天给植物换水时,文竹的根居然从花盆底部伸吊了出来,以前都没有这种情况来着&…

探索智慧校园,引领数字化教育浪潮

在21世纪的教育版图上,智慧校园进一步发展。这是一场深度融合信息技术与教育实践的深刻转型,它不仅仅是在校园里简单叠加智能设备,而是一种从教育理念到实践模式全方位的革新。智慧校园如同一座桥梁,连接着过去与未来,…

【OrangePiKunPengPro】 linux下编译、安装Boa服务器

OrangePiKunPengPro | linux下编译、安装Boa服务器 时间:2024年6月7日21:41:01 1.参考 1.boa- CSDN搜索 2.Boa服务器 | Ubuntu下编译、安装Boa_ubuntu安装boa-CSDN博客 3.i.MX6ULL—ElfBoard Elf1板卡 移植boa服务器的方法 (qq.com) 2.实践 2-1下载代码 [fly752fa…

算法设计与分析 实验1 算法性能分析

目录 一、实验目的 二、实验概述 三、实验内容 四、问题描述 1.实验基本要求 2.实验亮点 3.实验说明 五、算法原理和实现 问题1-4算法 1. 选择排序 算法实验原理 核心伪代码 算法性能分析 数据测试 选择排序算法优化 2. 冒泡排序 算法实验原理 核心伪代码 算…

【Pycharm】设置双击打开文件

概要 习惯真可怕。很多小伙伴用习惯了VsCode开发,或者其他一些开发工具,然后某些开发工具是单击目录文件就能打开预览的,而换到pycharm后,发现目录是双击才能打开预览,那么这个用起来就特别不习惯。 解决办法 只需一…

摄影师在人工智能竞赛中与机器较量并获胜

摄影师在人工智能竞赛中与机器较量并获胜 自从生成式人工智能出现以来,由来已久的人机大战显然呈现出一边倒的态势。但是有一位摄影师,一心想证明用人眼拍摄的照片是有道理的,他向算法驱动的竞争对手发起了挑战,并取得了胜利。 迈…

大疆Pocket3手持记录仪格式化恢复方法

大疆Pocket系列是手持类产品,此类产品处理过不少像Pocket、Pocket2、Pocket3基本上涉及Pocket全系列,今天来看一个Pocket3误格式化之后的恢复方法。 故障存储: 120G存储卡 /文件系统:exFAT 故障现象: 在备份视频数据时由于操作失误导致初…

【云岚到家】-day03-1-门户等缓存方案选择

【云岚到家】-day03-1-门户-缓存方案选择 1 门户1.1 门户简介1.2 常见的技术方案1.2.1 需求1.2.2 常见门户1.2.2.1 Web门户1.2.2.2 移动应用门户1.2.2.3 总结 2 缓存技术方案2.1 需求分析2.1.1 界面原型2.2.2 缓存需求 3 SpringCache入门3.1 基础概念3.1.1 Redis客户端3.1.2 Sp…

【linux】Linux分析cpu问题

CPU使用率高怎么分析: 首先先看哪些线程占用资源高看每个线程在干啥(类似windows系统的任务管理器) 步骤: 定位应用进程 pid jps -l # 查看进程找到线程 tid top -Hp {pid}将 tid 转换成十六进制 printf "%x\n" {…

人工智能对零售业的影响

机器人、人工智能相关领域 news/events (专栏目录) 本文目录 一、人工智能如何改变零售格局二、利用人工智能实现购物体验自动化三、利用人工智能改善库存管理四、通过人工智能解决方案增强客户服务五、利用人工智能分析消费者行为六、利用 AI 打造个性化…

[Qt的学习日常]--常用控件1

前言 作者:小蜗牛向前冲 名言:我可以接受失败,但我不能接受放弃 如果觉的博主的文章还不错的话,还请点赞,收藏,关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 目录 一、什么是控…

机器真的能思考、学习和智能地行动吗?

In this post, were going to define what machine learning is and how computers think and learn. Were also going to look at some history relevant to the development of the intelligent machine. 在这篇文章中,我们将定义机器学习是什么,以及…

SolarLab - hackthebox

简介 靶机名称:SolarLab 难度:中等 靶场地址:https://app.hackthebox.com/machines/SolarLab 本地环境 靶机IP :10.10.11.16 ubuntu渗透机IP(ubuntu 22.04):10.10.16.17 windows渗透机IP(windows11&…

AMD平台,5600X+6650XT,虚拟机安装macOS 14(2024年6月)

AMD平台安装macOS 14的麻烦,要比Intel平台多的多,由于macOS从13开始,对CPU寄存器的读取进行了改变,导致AMD平台只要安装完macOS 13及以后版本,开机后就报五国语言错误,不断重启。改vmx文件,被证…

ZED双目相机环境配置

官方资料:stereolabs/zed-python-api: Python API for the ZED SDK (github.com) 1,配置ZED相机环境 1.安装CUDA 查看电脑是否安装CUDA,安装过程可参考以下博文: 如何选择匹配的CUDA版本:https://blog.csdn.net/iam…