没有合适的资源?快使用搜索试试~ 我知道了~
Any graph can be a minimum dependency graph_杨宗翰1
需积分: 0 0 下载量 34 浏览量
2022-08-03
17:46:43
上传
评论
收藏 53KB PDF 举报
温馨提示
试读
1页
Any graph can be a minimum dependency graphWe call a dependency graph D minimum,
资源详情
资源评论
资源推荐
Any graph can be a minimum dependency graph
YANG Zonghan
April 7, 2020
Definition We call a dependency graph D minimum, if no dependency graph D
′
on the same set of
events that have fewer edges in D.
Theorem Any graph can be a minimum dependency graph.
Proof. Let G = (V, E). Assign every edge with a label of [|E|], using bijection num : E 7→ [|E|]. Consider
a set of mutually independent events {E
1
, E
2
, · · · , E
|E|
} on some probability space Ω. Construct event for
every vertex v ∈ V that
E
v
=
∩
(u,v)∈E
E
num
(
(u,v)
)
The graph is obviously a dependency graph. Also, it’s minimum: any graph G
′
with fewer edges doesn’t
have at least one edge in G, which is independent in the G
′
but not in G.
Acknowledgement Thanks 毛昕渝 for checking the validity.
1
我就是月下
- 粉丝: 25
- 资源: 336
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0