首页 > 学院 > 开发设计 > 正文

Unit 2-Lecture8: Degrees & Isomorphism

2019-11-14 12:29:54
字体:
来源:转载
供稿:网友

1 Simple graphs

Simple graphs are defined as digraphs in which edges are undirected.

2 Handshaking Lemma

The sum of the degrees of the vertices in a graph equals twice the number of edges.

3 Some Common Graphs

A complete graph Kn has n vertices and an edge between every two vertices, for a total of n(n-1)/2 edges.An n-node graph containing n-1 edges in sequence is known as a line graph Ln.If we add the edge < vn — v1 > to the line graph Ln, we get a graph called a lengthn cycle Cn.

4 Isomorphism

two graphs are isomorphic when there is an edge-PReserving matching of their vertices.isomorphism is an equivalence relation.If some property preserved by isomorphism differs for two graphs, then they’re not isomorphic: # of nodes,# of edges,degree distributions, ….
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表