The Laplacian matrix of a graph $G$ is $L(G)=D(G)-A(G)$, where $A(G)$ is the adjacency matrix and $D(G)$ is the diagonal matrix of vertex degrees. According to the Matrix-Tree Theorem, the number of spanning trees in $G$ is equal to any cofactor of an entry of $L(G)$. A rooted forest is a union of disjoint rooted trees. We consider the matrix $W(G)=I+L(G)$ and prove that the $(i,j)$-cofactor of $W(G)$ is equal to the number of spanning rooted forests of $G$, in which the vertices $i$ and $j$ belong to the same tree rooted at $i$. The determinant of $W(G)$ equals the total number of spanning rooted forests, therefore the $(i,j)$-entry of the matrix $W^{-1}(G)$ can be considered as a measure of relative ''forest-accessibility'' of vertex $i$ from $j$ (or $j$ from $i$). These results follow from somewhat more general theorems we prove, which concern weighted multigraphs. The analogous theorems for (multi)digraphs are also established. These results provide a graph-theoretic interpretation for the adjugate to the Laplacian characteristic matrix.


翻译:暂无翻译

0
下载
关闭预览

相关内容

【ACL2020】多模态信息抽取,365页ppt
专知会员服务
141+阅读 · 2020年7月6日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
25+阅读 · 2019年10月18日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
57+阅读 · 2019年10月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
145+阅读 · 2019年10月12日
【NeurIPS2019】图变换网络:Graph Transformer Network
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Focal Loss for Dense Object Detection
统计学习与视觉计算组
11+阅读 · 2018年3月15日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
From Softmax to Sparsemax-ICML16(1)
KingsGarden
71+阅读 · 2016年11月26日
国家自然科学基金
1+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
PnP for Two-Dimensional Pose Estimation
Arxiv
0+阅读 · 2023年12月20日
Arxiv
0+阅读 · 2023年12月20日
Arxiv
0+阅读 · 2023年12月19日
Arxiv
0+阅读 · 2023年12月19日
Arxiv
0+阅读 · 2023年12月18日
Arxiv
0+阅读 · 2023年12月18日
DFT-Based Channel Estimation for Holographic MIMO
Arxiv
0+阅读 · 2023年12月17日
Arxiv
0+阅读 · 2023年12月15日
Arxiv
0+阅读 · 2023年12月15日
Arxiv
0+阅读 · 2023年12月14日
VIP会员
相关资讯
【NeurIPS2019】图变换网络:Graph Transformer Network
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
26+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Focal Loss for Dense Object Detection
统计学习与视觉计算组
11+阅读 · 2018年3月15日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
From Softmax to Sparsemax-ICML16(1)
KingsGarden
71+阅读 · 2016年11月26日
相关论文
PnP for Two-Dimensional Pose Estimation
Arxiv
0+阅读 · 2023年12月20日
Arxiv
0+阅读 · 2023年12月20日
Arxiv
0+阅读 · 2023年12月19日
Arxiv
0+阅读 · 2023年12月19日
Arxiv
0+阅读 · 2023年12月18日
Arxiv
0+阅读 · 2023年12月18日
DFT-Based Channel Estimation for Holographic MIMO
Arxiv
0+阅读 · 2023年12月17日
Arxiv
0+阅读 · 2023年12月15日
Arxiv
0+阅读 · 2023年12月15日
Arxiv
0+阅读 · 2023年12月14日
相关基金
国家自然科学基金
1+阅读 · 2017年12月31日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员