刚才上课时想到的问题
图论中的Hamilton回路和Euler回路是否在仿射中互为对射?如果是的话,为什么我们的教材上却说Hamilton回路存在的充要条件还未找到(Euler回路存在的充要条件早就已经由Euler本人给出了的,而照理说Hamilton正好与之对偶,不也就出来了吗)?
还有,图同构的条件是否真的如教材上所说的还未给出?而我感觉只需要将它表示成矩阵形式,然后看对应两个矩阵的结构是否一致不就行了吗(当然,"结构"的一致性判断还包括很多)?
| 论坛嘉宾: 萍踪浪迹 gauge 季候风 |
|
ET  发表文章数: 15
|
 THE DAY WITHOUT SCIENCE,
|
||
|
萍踪浪迹  发表文章数: 1051
|
哦＾我一向怕图论啊，期望高手回答
漫漫长夜不知晓 日落云寒苦终宵
|
||
|
Tom 发表文章数: 55
|
声明：我不搞图论.
RE: 而我感觉只需要将它表示成矩阵形式,然后看对应两个矩阵的结构是否一致不就行了吗 谁不知道！那你要亲自数一下，不是更清楚了吗？还要什么条件. 如是1000000个点，你能行吗?
|
||
|
一剑一壶酒 发表文章数: 34
|
不知道EP兄所说的仿射中互为对射的意思,图论中的概念太不统一了.
不过以前学的时候,G是E的,iff,L(G)(即G的line graph)是H的,不过不是每个图都能写成某个图的line graph,这是不能用这种方法判定H图的原因 一把剑，一壶酒，我将何去何从？
|
||
|
ET 发表文章数: 15
|
第一个问题
我回去又看了看，这个对射是存在的，不过我发现需要定义一个所谓的虚点，因为存在这种可能，即一个顶点可能连上了多于2条边，但显然，我们不能由对射得到一条有多于2个端点的直线，因此，这种情况必须克服。 第二个问题， 的确，一个一个算当然与此类似，但矩阵方法很大程度上可以简化运算，并可以给出一些较直观的判别定理，即可“成批”的解决问题，而我现在正在深入，以后等我有了结果再来论证以下。 谢谢！ THE DAY WITHOUT SCIENCE,
|
||
|
ni_o  发表文章数: 33
|
ET老弟：这两个问题（Hamilton回路存在的充要条件&图同构的条件）是超超超超难的东东！如果你能找到Hamilton回路存在的充要条件并提供一个多项式算法，你就可以获得***奖，如果你提供一个强的图同构的条件你同样***
呵呵，我们要做的事还很多。 吾爱吾师,吾更爱真理.
|
Re: 刚才上课时想到的问题