标签: graph-theory

平面文件和关系数据库为我们提供了一种序列化结构化数据的机制.XML非常适合序列化非结构化树状数据.

但是很多问题最好用图表来表示.例如,热模拟程序将通过电阻边缘与彼此连接的温度节点一起工作.

那么序列化图形结构的最佳方法是什么？我知道XML在某种程度上可以做到这一点 - 就像关系数据库可以序列化复杂的对象网络一样:它通常可以工作,但很容易变得丑陋.

我知道graphviz程序使用的点语言,但我不确定这是最好的方法.这个问题可能是学术界可能正在研究的问题,我很乐意参考讨论这个问题的任何论文.

每逢圣诞节,我们都会在家里为礼物换取名字.这通常涉及多次重绘,直到没有人拉他们的配偶.因此,今年我编写了自己的名字绘图应用程序,其中包含一堆名称,一堆不允许的配对,并向所有人发送电子邮件与他们选择的礼品.

现在,算法就像这样(在伪代码中):

function DrawNames(list allPeople, map disallowedPairs) returns map
    // Make a list of potential candidates
    foreach person in allPeople
        person.potentialGiftees = People
        person.potentialGiftees.Remove(person)
        foreach pair in disallowedPairs
            if pair.first = person
               person.Remove(pair.second)

    // Loop through everyone and draw names
    while allPeople.count > 0
        currentPerson = allPeople.findPersonWithLeastPotentialGiftees
        giftee = pickRandomPersonFrom(currentPerson.potentialGiftees)
        matches[currentPerson] = giftee
        allPeople.Remove(currentPerson)
        foreach person in allPeople
            person.RemoveIfExists(giftee)

    return matches

知道更多关于图论的人是否知道某种算法在这里会更好用？为了我的目的,这是有效的,但我很好奇.

编辑:由于电子邮件不久前出现了,我只是希望学习一些东西,我将其重新描述为图论问题.我对排除所有成对的特殊情况不太感兴趣(如配偶没有相互获得).我对那些有足够排除条件的情况更感兴趣,因为找到任何解决方案都会成为困难的部分.我上面的算法只是一个简单的贪心算法,我不确定在所有情况下都会成功.

从完整的有向图和顶点对列表开始.对于每个顶点对,删除第一个顶点到第二个顶点的边.

目标是得到一个图形,其中每个顶点有一条边进入,一条边离开.

是否有算法可以找到无向图的生成树,从而最大限度地减少连接到多个边的顶点数？

例如,给定一个4 x 4网格图,我们希望在左边找到一个生成树(它有7个顶点连接到多个边)而不是右边的生成树(有12个):

编辑:如果我们只考虑平面图(甚至只是网格图),这个问题会更简单吗？

通常当我不得不走图表时,由于空间复杂度较低,我总是使用深度优先搜索.我诚实从未见过呼吁广度优先搜索,但我的经验的情况是相当有限的.

什么时候使用广度优先搜索是有意义的？

更新:我想我的答案在这里表示我已经使用了BFS(因为我觉得这是一个DFS)的情况.我仍然很想知道,为什么它在这种情况下很有用.

我的女朋友在接受采访时得到了这个问题,我非常喜欢它,我以为我会分享它......写一个接收字典的算法(字数组).数组按字典顺序排序,但abc顺序可以是任何内容.例如,它可以是z,y,x,..,c,b,a.或者它可能完全搞砸了:d,g,w,y,......它甚至不需要包含所有的abc字母,最后它根本不必是字母.它可以是形成字符串的任何符号.例如,它可以由5,？,!,@,？组成......你明白了.由您的算法决定发现字母是什么(简单部分).

算法应返回符号的正确词典顺序.

注意事项/需要考虑的事项:1.对于给定的字典,您是否总能发现所有字母的完整顺序？考虑一个只有1个单词,多于1个符号的字典...... 2.你不能认为字典是没有错误的.该算法应确定字典是否包含矛盾并输出存在错误.3.提示:想一个好的数据结构来表示你在符号之间发现的关系.这应该使问题更容易.

我明天可能会发布我的解决方案.我绝不会声称它是最有效的.我想先看看其他人的想法.希望你喜欢这个问题

PS我认为发布解决方案的最佳格式是使用伪代码,但我将此留待您考虑

鉴于城市列表和每个城市之间的飞行成本,我试图找到访问所有这些城市的最便宜的行程.我目前正在使用MATLAB解决方案找到最便宜的路线,但我现在想修改算法以允许以下内容:

1. 重复节点 - 应允许重复节点,因为通过枢纽城市旅行通常会导致更便宜的路线
2. 动态边缘权重 - 返回/往返航班与两个等效单程航班的成本不同(通常较低)

目前,我忽略了航班日期的问题,并假设可以从任何城市前往任何其他城市.

有没有人有任何想法如何解决这个问题？我的第一个想法是使用像GA或ACO这样的进化优化方法来解决第2点,并根据行程中是否包含返程/往返航班来评估目标函数时简单地调整边权重,但也许其他人有更好的理念.

(注意:我使用的是MATLAB,但我不是专门寻找编码解决方案,更多的是关于可以使用哪种算法的高级想法.)

编辑 - 在考虑了这个之后,允许"重复节点"似乎过于松散了约束.我们可以进一步约束问题,以便尽管可以重复访问节点,但每个有向边只能访问一次.忽略任何不止一次包含同一航班的行程似乎是合理的.

我正在寻找社区检测算法的实现,例如Girvan-Newman算法(2002).我访问了该领域的几位研究人员的网站(Newman,Santo等)但无法找到任何代码.我想有人在那里发布了这些算法的实现(甚至可能是一个工具包？),但我似乎无法找到它.

我有一个大的(> 1000)有向无环图集,每个图都有一个大的(> 1000)顶点集.顶点被标记,标签的基数很小(<30)

我想识别(我的)在整个图表集中频繁出现的子结构.

1. 子结构是至少两个具有特定标签的直接连接顶点的图.这样的子结构可以在给定输入图中的一个或多个中出现一次或多次.例如,"a [带有两个直接连接的子标记为B的顶点A]在图U中出现两次,在图V中出现一次".
2. 我们正在寻找的子结构必须遵守一组预先给定的规则,这些规则在顶点的标签上进行过滤.作为示例:如果子图是"标记为A的顶点,其具有标记为B的至少一个直接连接的子节点并且不是标记为U或V的顶点的直接连接的兄弟节点",则包含标记为A的顶点的子结构是有趣的..不符合这些规则的子结构可能会出现在输入图中,但对搜索不感兴趣.

我们要查找的输出是给定图形中的子结构列表及其(出现次数).

我试图调查事物并且(因为它似乎总是发生在我身上)问题是NP完全的.据我所知,gSpan是解决这个问题最常用的算法.但是,如上所述,我不是在图中寻找任何常见的子结构,而只是那些遵守某些规则的子结构.人们应该能够如此使用它以减少搜索空间.

有关如何解决此问题的任何见解？

更新:我应该补充一点,上述规则可以在一定程度上递归.例如,"标记为A且具有至少两个标记为B的子节点的顶点,每个子节点具有至少一个标记为A的子节点".最大递归深度介于1到10之间.

更新II:指出我们不是在搜索已知或首选的子结构,而是在挖掘它们.没有勺针.

我一直在寻找一个实现(我正在使用networkx库.),它将找到无向加权图的所有最小生成树(MST).

我只能找到Kruskal算法和Prim算法的实现,这两种算法都只返回一个MST.

我已经看到了解决这个问题的论文(比如代表所有最小的生成树以及应用程序计数和生成),但是我的脑袋往往会在尝试思考如何将其转换为代码时出现爆炸.

事实上,我无法找到任何语言的实现!

为了找到树的直径,我可以从树中获取任何节点,执行BFS以找到距离它最远的节点,然后在该节点上执行BFS.与第二个BFS的最大距离将产生直径.

不过我不知道如何证明这一点？我尝试过对节点数量的归纳,但是有太多的情况.

任何想法将不胜感激......