标签: graph-theory

我遇到了一个问题,我在图中给出了N个节点,这些节点相互连接,然后给出一个矩阵,列出一个连接到另一个节点的节点(如果是,则为1,否则为0).我想知道如何最好地解决这个问题.我认为这些是邻接矩阵？但是我该如何实现......

基本上我试图摆脱这些是找到一个特定节点是否连接到给定集合'S'中的所有其他节点.选择的项目是否是集团......

我会感激任何提示.

这可能是一个没脑子,我一直在寻找,但似乎无法找到答案.对于只有两个顶点且它们之间只有一条边的图形,术语(以及任何替代术语)是什么？

这不是一个家庭作业问题:-)

我编写了一个源删除算法来对数据库中的表之间的某些依赖关系进行排序,结果发现我们有一个循环.为简单起见,假设我们有表A,B,C和D.边缘如下:

(A, B)
(B, A)
(B, C)
(C, D)
(D, A)

如您所见,这里有两个循环.一个在A和B之间,另一个在它们之间.这种类型总会在最大的周期中窒息吗？或者不一定是这样吗？

我目前正在开发一个需要解决以下问题的项目:

假设用户每次从他的移动设备访问网络上的特定资源时,系统都会存储他的位置(纬度,经度).

然后我需要能够告诉用户他用来访问该资源的"区域".而"区域"y可能意味着周长(中心和比率).

问题是我需要一些标准来丢弃孤立点,我需要一些标准来将剩余点分组为"区域".

我打赌必须有一些关于这个问题的文献,但问题是我甚至不知道引用这个问题的术语,以及从哪里开始寻找.

提前致谢 ;)

设G =(V,E)是无向图,s和t是V中的两个顶点.图的每个边都用红色或蓝色着色.我需要找到一种算法,找到s和t之间的路径,其中红色边缘的数量最少.

我想到了以下算法:一种改进的BFS算法

对于每个顶点,我们将使用一个名为"红色级别"的额外字段,它将指示从s到此顶点的路径上的最小红边数.一旦我们发现了一个新的顶点,我们将更新其红色级别字段.如果我们正在尝试探索已经发现的顶点,如果此顶点的红色级别大于当前红色级别,那么我们将从BFS树中删除此顶点并将其作为子节点的子节点插入其中正在探索,等等.所需的路径是在算法运行结束时连接BFS树中的s和t的路径.

我现在正在尝试证明这个算法是正确的,但收效甚微.我也不确定它是否确实是正确的.任何提示/想法？

找到图形外边缘的最佳方法是什么？

例如，这张图上的红边：

不知道这个算法有没有名字。这个名字足以帮助我在谷歌上找到一些东西。

我需要使用点在两条边之间添加一个链接。我需要添加到图中的是图片中显示的两条边之间标有“b”的红色链接。

源代码如下：

digraph { 
    a -> b; 
    a -> c; 
} 

在我学会了如何确定有向图是否具有1个拓扑排序之后,如果有一种方法可以确定是否存在具有2个拓扑排序的图,我有点好奇.首先,是否存在具有2个拓扑排序的图的真实情况？

我学会了使用哈密尔顿路径来确定DAG是否具有唯一的拓扑排序.这是否适用于此？谢谢

通常，为了代表Lisp中的基本无向图，我可以创建父节点及其对应的子节点的列表，如本问题所述（为方便起见，在下面进行了说明）。

该图产生边的列表：

(1 (2 6 7 8) 3 (4 (9 12)) 5 (10 11)) 

这在树或任何其他无向图的情况下有效。但是，当我们要表示一个有向无环图（其中每个节点可以有多个父级）时，这种表示形式就会失效：

现在，节点8具有多个父节点（2、3），但是当我们尝试表示它时，我们将无法判断节点8是否连接到两个父节点，或者是否存在两个节点8：

(1 (2 6 7 8) (3 8) (4 (9 12)) (5 10 11))

对于具有唯一节点的图，我们当然可以做出这种假设，但是据我所知，DAG可以具有重复的节点...那么我们如何处理呢？此外，我们如何在Lisp中将其表示为列表？

我有一个程序可以检索PubMed出版物的列表，并希望建立共同作者的图表，这意味着我想为每篇文章添加每位作者（如果尚不存在）作为顶点并添加无向边（或增加）它的权重）。

我设法编写了该程序的第一个程序，该程序检索了每个出版物的作者列表，并且了解我可以使用NetworkX库来构建图形（然后将其导出到GraphML for Gephi），但是无法全神贯注于如何转换图形。 “列表列表”到图形。

这是我的代码。非常感谢你。

### if needed install the required modules
### python3 -m pip install biopython
### python3 -m pip install numpy

from Bio import Entrez
from Bio import Medline
Entrez.email = "rja@it.com"
handle = Entrez.esearch(db="pubmed", term='("lung diseases, interstitial"[MeSH Terms] NOT "pneumoconiosis"[MeSH Terms]) AND "artificial intelligence"[MeSH Terms] AND "humans"[MeSH Terms]', retmax="1000", sort="relevance", retmode="xml")
records = Entrez.read(handle)
ids = records['IdList']
h = Entrez.efetch(db='pubmed', id=ids, rettype='medline', retmode='text')
#now h holds all of the articles and their sections
records = …