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

【回溯算法】【Python实现】最大团问题

文章目录

    • @[toc]
      • 问题描述
      • 回溯算法
      • `Python`实现
      • 时间复杂性

问题描述

  • 给定无向图 G = ( V , E ) G = (V , E) G=(V,E),如果 U ⊆ V U \subseteq V UV,且对任意 u u u v ∈ U v \in U vU ( u , v ) ∈ E (u , v) \in E (u,v)E,则称 U U U G G G的完全子图

  • G G G的完全子图 U U U G G G的一个团当且仅当 U U U不包含在 G G G的更大的完全子图中, G G G的最大团是指 G G G中所含顶点数最多的团

  • 如果 U ⊆ V U \subseteq V UV且对任意 u u u v ∈ U v \in U vU,有 ( u , v ) ∉ E (u , v) \notin E (u,v)/E,则称 U U U G G G的空子图

  • G G G的空子图 U U U G G G的独立集当且仅当 U U U不包含在 G G G的更大的空子图中, G G G的最大独立集是 G G G中所含顶点数最多的独立集

  • 对于任意无向图 G = ( V , E ) G = (V , E) G=(V,E),其补图 G ˉ = ( V ′ , E ′ ) \bar{G} = (V^{'} , E^{'}) Gˉ=(V,E)定义为: V ′ = V V^{'} = V V=V E ′ = { ( u , v ) ∣ ( u , v ) ∉ E } E^{'} = \set{(u , v) \mid (u , v) \notin E} E={(u,v)(u,v)/E}

  • 如果 U U U G G G的完全子图,则它是 G ˉ \bar{G} Gˉ的空子图,反之亦然,因此, G G G的团与 G ˉ \bar{G} Gˉ的独立集之间存在一一对应关系,特别地, U U U G G G的最大团,当且仅当 U U U G ˉ \bar{G} Gˉ的最大独立集

  • 无向图 G G G G G G的补图 G ˉ \bar{G} Gˉ如下图所示

1


回溯算法

  • G G G的最大团和最大独立集问题都可以看作图 G G G的顶点集 V V V的子集选取问题,因此,可用子集树表示问题的解空间,解最大团问题的回溯法与解装载问题的回溯法十分相似
  • 设当前扩展结点 Z Z Z位于解空间树的第 i i i层,在进入左子树前,必须确认从顶点 i i i到已选入的顶点集中每个顶点都有边相连,在进入右子树前,必须确认还有足够多的可选择顶点,使得算法有可能在右子树中找到更大的团

Python实现

def find_maximum_clique(graph):n = len(graph)vertices = list(range(n))max_clique = []def is_clique(current_clique):# 约束函数: 判断给定的顶点集合是否构成一个团(完全子图)for i in range(len(current_clique)):for j in range(i + 1, len(current_clique)):if not graph[current_clique[i]][current_clique[j]]:return Falsereturn Truedef bound(current_clique, vertices):# 限界函数return len(current_clique) + len(vertices)def backtrack(vertices, current_clique):nonlocal max_cliqueif not vertices:if len(current_clique) > len(max_clique):max_clique.clear()max_clique.extend(current_clique)returnvertex = vertices.pop(0)current_clique.append(vertex)neighbors = []for v in vertices:if graph[vertex][v]:neighbors.append(v)# 选择当前顶点并加入团if is_clique(current_clique):backtrack(neighbors, current_clique)# 恢复回溯前状态current_clique.pop()# 不选择当前顶点if bound(current_clique, vertices) > len(max_clique):backtrack(vertices, current_clique)backtrack(vertices, [])return max_cliquegraph = [[0, 1, 0, 1, 1],[1, 0, 1, 0, 1],[0, 1, 0, 0, 1],[1, 0, 0, 0, 1],[1, 1, 1, 1, 0]
]maximum_clique = find_maximum_clique(graph)print(f'最大团: {maximum_clique}')
最大团: [0, 1, 4]

时间复杂性

  • 解最大团问题的回溯算法所需的计算时间为 O ( n 2 n ) O(n 2^{n}) O(n2n)

相关文章:

【回溯算法】【Python实现】最大团问题

文章目录 [toc]问题描述回溯算法Python实现时间复杂性 问题描述 给定无向图 G ( V , E ) G (V , E) G(V,E),如果 U ⊆ V U \subseteq V U⊆V,且对任意 u u u, v ∈ U v \in U v∈U有 ( u , v ) ∈ E (u , v) \in E (u,v)∈E,则称…...

CMakeLists.txt语法规则:foreach 循环基本用法

一. 简介 cmake 中除了 if 条件判断之外,还支持循环语句,包括 foreach()循环、while()循环。 本文学习 CMakeLists.txt语法中的循环语句。 CMakeLists.txt语法中 有两种 循环实现方式:foreach循环与 while循环。 二. CMakeLists.txt语法规则…...

redis集群-主从机连接过程

首先从机需要发送自身携带的replid和offset向主机请求连接 replid:replid是所有主机在启动时会生成的一个固定标识,它表示当前复制流的id,当从机第一次请求连接时,主机会将自己的replid发送给从机,从机在接下来的请求…...

去哪里找高清视频素材?推荐几个短视频素材免费网站

在数字时代,视频内容的质量直接影响观众的吸引力和留存率。尤其是高清、4K视频素材和可商用素材,它们在提升视觉质量和叙事深度方面起到了至关重要的作用。以下是一些国内外的顶级视频素材网站,它们提供的资源将为您的创作提供极大的支持和灵…...

从互联网医院源码到搭建:开发视频问诊小程序的技术解析

如今,视频问诊小程序作为医疗服务的一种新形式,正逐渐受到人们的关注和青睐。今天,小编将为您详解视频问诊小程序的开发流程。 一、背景介绍 互联网医院源码是视频问诊小程序开发的基础,它提供了一套完整的医疗服务系统框架&…...

【Linux】常见指令(二)

mv指令 mv命令是move的缩写,可以用来移动文件或者将文件改名(move (rename) files) 是Linux系统下常用的命令,经常用来备份文件或者目录 功能: 1.剪切文件或者目录 2.对文件或者目录进行重命名 常用选项: -f &#xf…...

python元类与C#、Java中的反射

Python的元类和C#中的反射 在概念上有一定的相似性,但它们的目的和使用方式有所不同。 Python的元类: 元类(Metaclass)是控制类创建的类。它们定义了类的创建过程,可以修改类的行为。元类通过定制类的创建过程&…...

Echart.js绘制时间线并绑定事件

<template><div id"app"><!-- 定义一个具有指定宽高的容器&#xff0c;用于渲染图表 --><div ref"timeline" style"width: 800px; height: 600px;"></div></div> </template><script> import *…...

Flutter弹窗链-顺序弹出对话框

效果 前言 弹窗的顺序执行在App中是一个比较常见的应用场景。比如进入App首页&#xff0c;一系列的弹窗就会弹出。如果不做处理就会导致弹窗堆积的全部弹出&#xff0c;严重影响用户体验。 如果多个弹窗中又有判断逻辑&#xff0c;根据点击后需要弹出另一个弹窗&#xff0c;这…...

1290.二进制链表转整数

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。 请你返回该链表所表示数字的 十进制值 。 示例 1&#xff1a; 输入&#xff1a;head [1,0,1] 输出&#xff1a;5 解释&#xff1a;二进制数 (101) 转化为十进制…...

P8803 [蓝桥杯 2022 国 B] 费用报销

P8803 [蓝桥杯 2022 国 B] 费用报销 分析 最值问题——DP 题意分析&#xff1a;从N张票据中选&#xff0c;且总价值不超过M的票据的最大价值&#xff08;背包问题&#xff09; K天限制 一、处理K天限制&#xff1a; 1.对于输入的是月 日的格式&#xff0c;很常用的方式是…...

【Android】Kotlin学习之Lambda表达式

java和kotlin对比 Lambda语法 Lambda隐形参数 it 也可以不使用指定的名称it, 可以 自定义 Lambda 使用下划线...

YOLOv5-7.0改进(四)添加EMA注意力机制

前言 关于网络中注意力机制的改进有很多种&#xff0c;本篇内容从EMA注意力机制开始&#xff01; 往期回顾 YOLOv5-7.0改进&#xff08;一&#xff09;MobileNetv3替换主干网络 YOLOv5-7.0改进&#xff08;二&#xff09;BiFPN替换Neck网络 YOLOv5-7.0改进&#xff08;三&…...

TCP协议的确认应答机制

TCP&#xff08;Transmission Control Protocol&#xff09;是一种面向连接的、可靠的、基于字节流的传输层协议&#xff0c;它在网络通信中扮演着至关重要的角色。其中&#xff0c;确认应答机制是TCP协议中的一个核心概念&#xff0c;它确保了数据的可靠传输。本文将详细介绍J…...

【论文阅读笔记】MAS-SAM: Segment Any Marine Animal with Aggregated Features

1.论文介绍 MAS-SAM: Segment Any Marine Animal with Aggregated Features MAS-SAM&#xff1a;利用聚合特征分割任何海洋动物 Paper Code(空的) 2.摘要 最近&#xff0c;分割任何模型&#xff08;SAM&#xff09;在生成高质量的对象掩模和实现零拍摄图像分割方面表现出卓越…...

C语言中的精确宽度类型

概述 在 C 语言标准库 <stdint.h> 中定义了一系列精确宽度的整数类型&#xff0c;这些类型保证了它们的位数宽度&#xff0c;从而允许编写跨平台的可移植代码。以下是一些常用的精确宽度整数类型&#xff1a; int8_t: 8位有符号整数uint8_t: 8位无符号整数int16_t: 16位…...

大数据比赛-环境搭建(一)

1、安装VMware Workstation 链接&#xff1a;https://pan.baidu.com/s/1IvSFzpnQFl3svWyCGRtEmg 提取码&#xff1a;ukpo 内有安装包及破解方式&#xff0c;安装教程。 2、下载Ubuntu系统 阿里巴巴开源镜像站-OPSX镜像站-阿里云开发者社区 (aliyun.com) 点击下载&#xff…...

微信小程序原生组件使用

1、video组件使用 <view class"live-video"><video id"myVideo" src"{{videoSrc}}" bindplay"onPlay" bindfullscreenchange"fullScreenChange" controls object- fit"contain"> </video&g…...

[数据集][目标检测]纸箱子检测数据集VOC+YOLO格式8375张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;8375 标注数量(xml文件个数)&#xff1a;8375 标注数量(txt文件个数)&#xff1a;8375 标注…...

2024HW Linux应急响应基础学习

首先展示关于Linux的关键目录&#xff0c;这是应急响应查看的关键&#xff1a; 常用命令 top //查看进程资源的占用情况 ps -aux //查看进程 直接写ps aux也可以 netstat -antpl //查看网络连接 ls -alh /proc/pid //查看某个pid对应的可执行程序 pid记得修改 lsof /…...

Redis管理效率革命:AnotherRedisDesktopManager实战指南

Redis管理效率革命&#xff1a;AnotherRedisDesktopManager实战指南 【免费下载链接】AnotherRedisDesktopManager qishibo/AnotherRedisDesktopManager: Another Redis Desktop Manager 是一款跨平台的Redis桌面管理工具&#xff0c;提供图形用户界面&#xff0c;支持连接到Re…...

别再死记硬背了!用Python手把手教你实现数据库闭包自动计算器

用Python实现数据库闭包计算器&#xff1a;从理论到实战的自动化工具 闭包计算是数据库原理中的核心算法&#xff0c;但传统教材往往停留在抽象描述和手工演算阶段。作为曾经被各种箭头符号和递归推导折磨过的开发者&#xff0c;我决定用Python打造一个能自动计算闭包并可视化步…...

CentOS 7下OnlyOffice离线部署全攻略:从依赖包下载到一键配置(避坑指南)

CentOS 7下OnlyOffice离线部署全攻略&#xff1a;从依赖包下载到一键配置&#xff08;避坑指南&#xff09; 在企业内网或安全隔离环境中部署文档协作平台时&#xff0c;OnlyOffice凭借其开源特性和丰富的编辑功能成为首选方案。本文将深入探讨如何在CentOS 7系统中实现完全离线…...

GraphRAG:当 RAG 遇上知识图谱,信息检索从此不一样了

假设你把公司过去三年的所有周报、会议纪要、项目文档丢进一个 RAG 系统&#xff0c;然后问它&#xff1a;“过去一年里&#xff0c;研发团队和产品团队之间的主要分歧有哪些&#xff1f;”——大概率你会得到几段看起来相关的文字片段&#xff0c;但拼不出一个完整的答案。 这…...

vLLM-v0.17.1实操手册:vLLM服务升级策略与滚动更新最佳实践

vLLM-v0.17.1实操手册&#xff1a;vLLM服务升级策略与滚动更新最佳实践 1. vLLM框架概述 vLLM是一个专为大型语言模型(LLM)设计的高性能推理和服务库&#xff0c;最新发布的v0.17.1版本带来了多项性能优化和功能增强。这个开源项目最初由加州大学伯克利分校的研究团队开发&am…...

Qwerty Learner 终极指南:通过打字训练快速掌握英语词汇的免费工具

Qwerty Learner 终极指南&#xff1a;通过打字训练快速掌握英语词汇的免费工具 【免费下载链接】qwerty-learner 项目地址: https://gitcode.com/GitHub_Trending/qw/qwerty-learner 想要在敲击键盘的同时轻松记忆英语单词吗&#xff1f;Qwerty Learner 正是为你设计的…...

DataGuard运维避坑指南:当备库遇到ORA-01578坏块时的完整恢复流程

DataGuard运维实战&#xff1a;备库ORA-01578坏块诊断与FROM SERVICE精准修复 凌晨三点&#xff0c;当告警短信突然亮起"ORA-01578: ORACLE data block corrupted"的红色提示时&#xff0c;作为DBA的你很清楚这意味着什么——这不仅是简单的坏块问题&#xff0c;更是…...

agent实习面经(十一)

来自网络&#xff0c;侵删 先完成&#xff0c;再完美 某东&#xff0c;某节1.LLM 为什么有幻觉&#xff0c;如何减少 LLM 幻觉&#xff1f;1.1概率生成机制&#xff1a;LLM 本质是基于统计概率预测下一个 token&#xff0c;而非检索事实数据库。当训练数据中缺乏确切信息或模…...

FastAPI流式AI接口设计陷阱大全(2024高频真题+源码级调试实录)

第一章&#xff1a;FastAPI流式AI接口设计陷阱大全&#xff08;2024高频真题源码级调试实录&#xff09;流式响应被中间件静默截断 FastAPI 默认启用的 Starlette 中间件&#xff08;如 HTTPSRedirectMiddleware 或自定义日志中间件&#xff09;可能在未显式处理 StreamingResp…...

**Modbus协议深度解析:基于Python的TCP通信实战与发散创新应用**在工业自动化领域,**Modbus协议

Modbus协议深度解析&#xff1a;基于Python的TCP通信实战与发散创新应用 在工业自动化领域&#xff0c;Modbus协议因其简单、稳定和开放性成为最广泛使用的串行通信标准之一。本文将从底层原理出发&#xff0c;深入剖析 Modbus TCP 的数据帧结构&#xff0c;并结合 Python 实现…...