h**********y
发帖数: 1293 | 1 how many connected tripatite graph are there,
say 3 partie of size 8,9,11. | t****a
发帖数: 1212 | | l*****a
发帖数: 14598 | 3 同看不懂
【在 t****a 的大作中提到】
: 太难了，题目都看不懂。能请解释一下么？
| g*********e
发帖数: 14401 | 4 https://www.google.com/search?q=tripartite&hl=en&safe=off&tbo=d&rlz=1C1CHMO_
enUS495&source=lnms&tbm=isch&sa=X&ei=KZH4UK6FOYqxigKZh4GwDw&ved=0CAcQ_AUoAA&
biw=1284&bih=772 | h**********y
发帖数: 1293 | 5 求 联通 triparitite 图的数目，
每个partite 节点 数目分别是8，9，11
1，1，1可能数目是4
1，1，2可能数目是14
【在 t****a 的大作中提到】
: 太难了，题目都看不懂。能请解释一下么？
| t****a
发帖数: 1212 | 6 还是看不懂。解释一下名词，还有111,112你怎么算出来的好么？
要是面试官这样问问题，我自己就先崩溃了。
【在 h**********y 的大作中提到】
: 求 联通 triparitite 图的数目，
: 每个partite 节点 数目分别是8，9，11
: 1，1，1可能数目是4
: 1，1，2可能数目是14
| h**********y
发帖数: 1293 | 7 tripartite graph,
三个组每个组有8，9，11个节点
求所有可能的联通graph数目（，满足从任何一个点可以到达任何另外一个点。由于是
tripartitie graph，就像bipartite一样，组内点不能直接连）
1，1，2可以自己画出来。。
【在 t****a 的大作中提到】
: 还是看不懂。解释一下名词，还有111,112你怎么算出来的好么？
: 要是面试官这样问问题，我自己就先崩溃了。
| h**********y
发帖数: 1293 | 8 原题比较啰嗦
The Kanto, Johto, and Sinnoh regions would like to facilitate travel among
themselves by building airports in all of their major towns. In total, they
are hoping to build the following numbers of airports:
* 9 in Kanto
* 8 in Johto
* 11 in Sinnoh
The slogan for their campaign reads, Fly from any city to any city!* with
fine print that reads, *Transfer flights may be necessary.
How many possible flight networks are there that satisfy the advertised
slogan? Note the following caveats:
* All flight paths in the network must be bi-directional.
* The airports refuse to establish direct flights between cities within
the same region since trainers can simply fly on Pokemon to do this.
* However, in order to stay true to their slogan, they must nonetheless
allow the possibility of intra-city plane travel via transfer flights.
【在 t****a 的大作中提到】
: 还是看不懂。解释一下名词，还有111,112你怎么算出来的好么？
: 要是面试官这样问问题，我自己就先崩溃了。
| b*****n
发帖数: 482 | 9 111: C(3,3) + C(2,3) = 4 // C(3, 3)表示3条边中取3条
112: C(5,5) + C(4,5) + (C(3,5)-C(3,3)*2)
C(5,5): 表示连通图有五条边，因为2个点那个set自己不能有边，所以总共六条边里只
有五条可以选
同理C(4,5)表示连通图有四条边，从总共5条边里选。C(3,5)表示5条边里选3条，但要
减去两种不连通的情况，就是2点set的其中一点与另两个set里的点构成一个三角形。
112的解也可以从111推出来，就是111的4个图基础上加入一个点，这个可以和另两个
set里的任意一个点连，或者同时和它们都有连接。这样就生成了12个图，多出来的两
个图是因为，当新加入的点和同时和另两个点连的时候，如果那两个点之间有边，就可
以砍掉，这样会多三个图，但其中一个与前面的有重复，所以总共14个。
但是我还没有找到通过以上这两个方法来简单地继续推导出下一步。如果知道f(i,j,k)
，能推出f(i+1,j,k), f(i,j+1,k), f(i,j,k+1)，就可以解了。题目中一共可能的edge
是8*9+9*11+8*11 = 259，最小连通图要17条边，也许直接暴力破？ :)
【在 t****a 的大作中提到】
: 还是看不懂。解释一下名词，还有111,112你怎么算出来的好么？
: 要是面试官这样问问题，我自己就先崩溃了。
| b*****n
发帖数: 482 | 10 贴个图
第一排对应111
第二排是从111的第一个图推出112的三张图
【在 b*****n 的大作中提到】
: 111: C(3,3) + C(2,3) = 4 // C(3, 3)表示3条边中取3条
: 112: C(5,5) + C(4,5) + (C(3,5)-C(3,3)*2)
: C(5,5): 表示连通图有五条边，因为2个点那个set自己不能有边，所以总共六条边里只
: 有五条可以选
: 同理C(4,5)表示连通图有四条边，从总共5条边里选。C(3,5)表示5条边里选3条，但要
: 减去两种不连通的情况，就是2点set的其中一点与另两个set里的点构成一个三角形。
: 112的解也可以从111推出来，就是111的4个图基础上加入一个点，这个可以和另两个
: set里的任意一个点连，或者同时和它们都有连接。这样就生成了12个图，多出来的两
: 个图是因为，当新加入的点和同时和另两个点连的时候，如果那两个点之间有边，就可
: 以砍掉，这样会多三个图，但其中一个与前面的有重复，所以总共14个。
| h**********y
发帖数: 1293 | 11 直接数connected的没法做。
要算disconnected的然后从总数里面减掉
【在 b*****n 的大作中提到】
: 111: C(3,3) + C(2,3) = 4 // C(3, 3)表示3条边中取3条
: 112: C(5,5) + C(4,5) + (C(3,5)-C(3,3)*2)
: C(5,5): 表示连通图有五条边，因为2个点那个set自己不能有边，所以总共六条边里只
: 有五条可以选
: 同理C(4,5)表示连通图有四条边，从总共5条边里选。C(3,5)表示5条边里选3条，但要
: 减去两种不连通的情况，就是2点set的其中一点与另两个set里的点构成一个三角形。
: 112的解也可以从111推出来，就是111的4个图基础上加入一个点，这个可以和另两个
: set里的任意一个点连，或者同时和它们都有连接。这样就生成了12个图，多出来的两
: 个图是因为，当新加入的点和同时和另两个点连的时候，如果那两个点之间有边，就可
: 以砍掉，这样会多三个图，但其中一个与前面的有重复，所以总共14个。
| h**********y
发帖数: 1293 | 12 真失望，
都没人来挑战这个题。。
想出来的话绝对功力大涨的！
they
【在 h**********y 的大作中提到】
: how many connected tripatite graph are there,
: say 3 partie of size 8,9,11.
|
|
