数学工程理科好的进~~有个小问题

Edinburgh

最近在想着一个问题，如果知道了身边人与人之间的关系信息，我怎么才能把相关人员聚合在一起？？？
也就是说，如果我已经知道了一组元素 以及对应的这些元素的关系，那我怎么才能把凡是有关连到的元素聚合在一起呢？

比如，若 a 喜欢 b  那么a和b就产生了联系，我标记成<a,b> ，同时 b 和 c 是好朋友  那么同理有<b,c> 的关系存在，于是间接的，a和c 也就会有一定的联系，于是便产生了<a,c>.  这叫“传递闭包”。

在比如

我喜欢用pelikan写字: <我，pelikan>.
pelikan讨厌万宝龙公司: <pelikan, 万宝龙>
于是就会有潜在的我跟万宝龙的关系<我，万宝龙>


那我现在的目的是 如果我知道两两元素的关系， 我怎么才能把这些集合最终聚集起来呢？
我爱你， 你爱他， 最后的结果是产生一个{我，你，他}。


我回忆了一下以前学过的传递闭包的概念比如

有 A这么个7个元素集合， 然后里面两两元素的关系写在R里面
A={a,b,c,d,e,f,g,h} ;R={<a,b>,<b,c>,<d,g>,<e,g>} ;

我现在能够利用传递闭包的数学计算得到：
t(R)={<a,b>,<a,c>,<b,c>,<d,g>,<e,g>}      

那我怎么才能进一步得到我想要的下面这几个集合呢？

{a，b，c} {d,e,g} {f}

rubanth

很h很暴力

aqua2001

从数学上说，首先你的“关系”必须给出明确的定义，而且这个关系至少要有传递性。事实上常用的是等价关系，这样能够很容易地把全集分成等价类。但我没完全听懂你的意思，你是想要算法呢还是什么别的？要是算法的话，最直观的方法是把关系用图表示出来以后，搜索（强）连通分支。

Edinburgh

从数学上说，首先你的“关系”必须给出明确的定义，而且这个关系至少要有传递性。事实上常用的是等价关系， ...
aqua2001 发表于 14/1/2011 12:55

    从A, R 到 t(R)={<a,b>,<a,c>,<b,c>,<d,g>,<e,g>} 我可以用现成的算法（比如wallshell）得到。
那从t(R)到 {a，b，c} {d,e,g} {f} 有没有什么方法可以快速得到？
因为t(R)里面现在只有5个二元关系对儿， 所以眼睛一看就可以写出来那3个集合了。如果t(R)里面存在海量比如1000万个关系对儿的话，那就得有个方法呀。

nil

program relation;
const
n=20;
var
rc:packed array[1..n]of integer;
k,m:integer;

procedure init;
var
  i:integer;
  st:string;
begin
  readln(st);
  assign(input,st);reset(input);
  readln(k,m);
  for i:=1 to k do rc[i]:=i;
end;

procedure main;
var
  i,j,p1,p2,t:integer;
begin
  for i:=1 to m do
   begin
    read(p1,p2);
    t:=rc[p2];
    for j:=1 to k do
      if rc[j]=t then rc[j]:=rc[p1];
   end;
end;

procedure print;
var
  i,t,a,b:integer;
begin
  read(t);
  for i:=1 to t do
   begin
    read(a,b);
    if rc[a]=rc[b] then writeln('YES') else writeln('NO');
   end;
  close(input);
end;

begin
init;
main;
print;
end.

nil

program relation;
const
n=20;
var
rc:packed array[1..n]of integer;
k,m:integer;

procedure init;
var
  i:integer;
  st:string;
begin
  readln(st);
  assign(input,st);reset(input);
  readln(k,m);
  for i:=1 to k do rc[i]:=i;
end;

procedure main;
var
  i,j,p1,p2,t:integer;
begin
  for i:=1 to m do
   begin
    read(p1,p2);
    t:=rc[p2];
    for j:=1 to k do
      if rc[j]=t then rc[j]:=rc[p1];
   end;
end;

procedure print;
var
  i,t,a,b:integer;
begin
  read(t);
  for i:=1 to t do
   begin
    read(a,b);
    if rc[a]=rc[b] then writeln('YES') else writeln('NO');
   end;
  close(input);
end;

begin
init;
main;
print;
end.

nil

中学时代写的Pascal小程序，解这个问题的。献丑

zenima123

这玩意是不是离散数学？

Edinburgh

这玩意是不是离散数学？
zenima123 发表于 14/1/2011 16:11

那个闭包传递是离散数学里的。。。
    今天突然幻想了一个现实中的问题，然后就想来想去，想到了貌似以前学习过的离散数学它可以帮上这个忙。。。

lacsylle

连线代表关系，节点上的所有元素构成了一个集合，还有许多其他这样的“树”，每一棵树都代表了一个符合lz要求的集合。

anderson997

本体？语义网？

Edinburgh

研究了一晚上终于搞定了。嘻嘻~~

笔谈

看到这种很头痛。。。

gutiwen

喜欢数学，喜欢与喜欢数学的人打交道。
上面这些对我来说是“天书”。

linrenzhi911

树的集合的传递性

大大小小

看着就头大

夕阳草0104

数学白痴路过，啥是离散数学？