标签: graph-theory

我喜欢Head First系列面向对象设计的书.这是一个非常温和而有趣的主题介绍.我目前正在学习数据结构课程并找到我们正在使用的文本(Kruse/Ryba数据结构和C++程序设计)非常干燥且难以理解.这主要是因为我认为我在数学领域的局限性.

有谁知道数据结构文本以较轻的风格编写,具有幽默感,仍然涵盖了二叉树,B树和图形等所有基础知识？

我有一个图表,我想要graphviz布局和可视化我.该图有122个边和123个节点.边缘有4种不同的类型,我希望它们在视觉上可以区分.但是我还没有决定最好的方法是什么,我想稍微调整一下表盘.不幸的是,我没有看到像边缘的"类"或"样式表"属性.我只能为每个边缘(大量重复)单独设置视觉属性.也许我错过了什么？毕竟可能有一些方法可以将边添加到4个不同的组然后设置组的样式,而不是单独的每个边？

这是算法设计手册中的练习.

考虑确定给定的无向图G =(V,E)是否包含长度为3的三角形或周期的问题.

(a)给O(| V | ^ 3)找到一个三角形(如果存在).

(b)改进算法以及时运行O(| V |·| E |).你可以假设| V | ≤| E |.

观察到这些边界为您提供了在G的邻接矩阵和邻接列表表示之间进行转换的时间.

这是我的想法:

(a)如果图形作为邻接列表给出,我可以通过O(| V | ^ 2)将列表转换为矩阵.然后我做:

for (int i = 0;i < n;i++) 
   for (int j = i+1;j < n;j++) 
   if (matrix[i][j] == 1) 
      for (int k = j+1;k < n;k++) 
         if (matrix[i][k] == 1 && matrix[j][k] == 1)
             return true;

这应该给出O(| V | ^ 3)来测试三角形.

(b)我的第一个直观是如果图形作为邻接列表给出,那么我将做一个bfs.例如,每当发现交叉边缘时if y-x is a cross edge,我会check whether parent[y] == parent[x], …

假设我有两个networkx图,G并且H:

G=nx.Graph()
fromnodes=[0,1,1,1,1,1,2]
tonodes=[1,2,3,4,5,6,7]
for x,y in zip(fromnodes,tonodes):
    G.add_edge(x,y)

H=nx.Graph()
fromnodes=range(2,8)
tonodes=range(8,14)
for x,y in zip(fromnodes,tonodes):
    H.add_edge(x,y)

加入两个networkx图表的最佳方法是什么？

我想保留节点名称(注意公共节点,2到7).当我使用时nx.disjoint_union(G,H),这没有发生:

>>> G.nodes()
[0, 1, 2, 3, 4, 5, 6, 7]
>>> H.nodes()
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
>>> Un= nx.disjoint_union(G,H)
>>> Un.nodes()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
# 

该H节点标签被改变(不是我想要的).我想在具有相同编号的节点处加入图形.

注意.这与NetworkX中的两个加权图组合 …

只是想知道是否有方便的networkx函数返回连接到图中的给定节点(或节点)(例如my_node_name)的边的列表(例如G).

我可以这样做:

edlist=[]
for ed in G.edges():
     if 'my_node_name' in ed:
            edlist.append(ed)

但期望可能有更好的方法？

我正在研究一个可以简化为图优化问题的问题,如下所示.

• 给出了一组彩色节点.它们都是未连接的,即图中没有边缘.

• 边缘将插入节点之间.

• 一个节点最多只能有4个边.

• 表格提供了边缘利润贡献的规则.

  例如.,

  • 连接红色到红色的边缘:利润为10

  • 连接红色到蓝色的边缘:利润是20

• 节点总数约为100.

• 颜色总数通常在20到30左右,但它可以高达50个.相应地,利润表(边缘)将是一个很长的列表,但它不会列出所有可能的组合.表中未指定的边的利润假定为零.

问题是优化连接(边缘),以使总利润最大化.

我想知道这个问题,或许是以某种其他方式,是已知的.如果是这样,请提供可能有帮助的任何指示.谢谢.

我一直在研究这三个,我在下面陈述我的推论.有人能告诉我,我是否已经足够准确地理解它们了吗？谢谢.

1. Dijkstra的算法仅在您拥有单个源并且您想知道从一个节点到另一个节点的最小路径时使用,但在这种情况下失败

2. 当任何所有节点都可以作为源时,使用Floyd-Warshall的算法,因此您希望最短距离从任何源节点到达任何目标节点.只有在出现负循环时才会失败

(这是最重要的一个.我的意思是,这是我最不确定的:)

3.Bellman-Ford像Dijkstra一样使用,当时只有一个来源.这可以处理负重量,它的工作方式与Floyd-Warshall相同,除了一个来源,对吗？

如果你需要看看,相应的算法是(礼貌的维基百科):

贝尔曼 - 福特:

 procedure BellmanFord(list vertices, list edges, vertex source)
   // This implementation takes in a graph, represented as lists of vertices
   // and edges, and modifies the vertices so that their distance and
   // predecessor attributes store the shortest paths.

   // Step 1: initialize graph
   for each vertex v in vertices:
       if v is source then v.distance := 0
       else v.distance := infinity
       v.predecessor := null

   // Step 2: relax …

是否存在用于在图中查找冗余边的既定算法？

例如,我想发现a-> d和a-> e是多余的,然后摆脱它们,如下所示:

=>

编辑:Strilanc很高兴能为我读懂我的想法."冗余"太强了,因为在上面的例子中,a-> b或a-> c都不被认为是冗余的,但a-> d是.

当前的GPU线程在某种程度上是有限的(内存限制,数据结构的限制,没有递归...).

你认为在GPU上实现图论问题是可行的吗？例如顶点覆盖？主导集？独立集？max clique？....

在GPU上使用分支定界算法是否可行？递归回溯？

任何人都知道我在哪里可以获得有向图的示例实现和用于在有向图上执行拓扑排序的示例代码？(最好用Java)