物理

一些图论基础定理(无证明)

$设图G为n阶图，则G中n个顶点的度之和等于边数的两倍$

$对于任意图G，奇度顶点的个数一定是偶数$

$有n个顶点且不含三角形的图G的最大边数为[\frac{n^2}{4}](托兰定理特殊)$

$设n阶图G不含K_{m+1}，这G的边数e(G)≤e_m(n)$

$当且仅当G与T_m(n)同构时取等(托兰定理)$

$设S=\{x_1,x_2,…,x_n\}是平面上直径为1的点集$

$则距离大于\frac{\sqrt{2}}{2}的点对的最大可能的数目是[\frac{n^2}{3}]$

$并且对每个n,存在直径为1的一个点集\{x_1,x_2,…,x_n\}$

$它恰好有[\frac{n^2}{3}]个点对，其距离大于\frac{\sqrt{2}}{2}$

$若树T的顶点数≥2，则T至少有两个度为1的点$

$设树T的顶点数为n，这它的边数e=n-1$

$设T有n个顶点e条边，则下面三个命题等价：$

$(1)T是数.(2)T无圈且e=n-1.(3)T连通且e=n-1.$

$有限图G为欧拉图⇔G是连通的且奇顶点个数等于0或2.$

$当且仅当奇顶点个数为0时，连通图G是一个圈$

$如果连通图G有2k个奇顶点，这图G可以用k笔画成，并且至少k笔$

$在二部图G=(V_1,V_2,E)中，如果|V_1|≠|V_2|，那么G一定无哈密顿圈.$

$如果|V_1|，|V_2|之差≥2，那么G一定无哈密顿链$

$G是n(≥3)阶简单图，且对每一对顶点v、v'有d(v)+d(v')≥n-1$

$则图G有哈密顿链(v和v'不相邻，则G有哈密顿圈)$

$G是n(≥3)阶简单图，如果每个顶点的度d(v)≥\frac{n}{2}$

$这图G一定存在哈密顿圈$

$如果图G有哈密顿图

$从G中去$$掉若干个点v_1,v_2,…,v_k及与他们关联的边得到图G'$

$那么G'的连通分支不超过k个$