0%

2-连通图的性质

G是块:G是无割点的连通图
H是G的块:H是G中极大无割点连通子图

块的等价定义(G是$v\geq 3$的连通图)

  • G是2-连通的(块)
  • G的任二顶点共圈
  • G的任一顶点与任一边共圈
  • G的任二边共圈
  • 对 $\forall u,v\in V(G)$ 及 $\forall e \in E(G)$ 存在 $(u,v)$ 路含有边 $e$
  • 对 $\forall u,v,w\in V(G)$,存在 $(u,v)$ 路含有顶点 $w$
  • 对 $\forall u,v,w\in V(G)$,存在 $(u,v)$ 路不含有顶点 $w$
阅读全文 »

割点和割边

割点定义

$v \in V(G):w(G-v)>w(G)$

割点的一个定理

如果点v是简单图G的一个割点,则边集$E[G]$可划分为两个非空子集$E_1$和$E_2$,使得边导出子图$G[E_1]$和$G[E_2]$恰好有一个公共顶点v。

阅读全文 »

Double Counting Principle

数学含义

$\sum_{i=1}^m\sum_{j=1}^n A[i][j]=\sum_{j=1}^n\sum_{i=1}^m A[i][j]$

lemma定理:

$\sum\limits_{v\in V}deg(v)=2|E|$

阅读全文 »

基本概念

定义:一集元素和它们之间关系的二元组(V,E),其中集合V称为顶点集,集合E是V中元素组成的某些无序对的集合,称为边集,顶点的数目$|V|$称为图的,边的数目$|E|$称为图的边数。

图示

定义:点表示顶点,线段表示边,绘制出平面表示图。

阅读全文 »

Abstract

本文考虑神经网络中图像的OoD的检测问题。作者提出了ODIN方法,这个方法的好处是不用对训练好的网络进行任何的更改。本文的理论基于两个手段————temperature scalinginput perturbation。这两个手段可以加大ID和OoD的softmax分布的差异,有助于检测。作者通过一系列的实验证明ODIN的方法对于各种网络结构和数据集都是兼容的,并且性能远好于baseline,可以称得上是一个state-of-the-art的方法。例如,设置网络架构为DenseNet,数据集为CIFAR-10和Tiny-ImageNet,ODIN相比于baseline把FPR at 95% TPR从34.7%降低到4.3%。

Introduction

现代神经网络在训练集和测试集样本来自同一个分布的时候效果很好。但现实世界部署的时候,往往测试集的分布是不受控制的。最近的工作表明,即使是输入不相关的数据,神经网络的预测结果也会偏高。对于分类器来说,遇到没见过的输入时给出一个不确定的反馈非常重要。因此,精确的检测OoD样本在视觉识别任务的实践中非常重要。

一个看上去比较直接的OoD检测方式就是扩大In-Distribution集合和Out-of-Distribution集合的规模。而OoD的数据往往是很有限的,这让再训练变得昂贵且难以处理。此外,为了确保神经网络在准确的给ID进行分类的同时,也能正确的检测出OoD,可能需要很大的神经网络架构,这使得训练过程更加复杂。

阅读全文 »