Graph Theory Note

* Graph property http://en.wikipedia.org/wiki/Graph_property

graph property or graph invariant

thay depends only on the abstract structure

** Definitions

goal: focus on the abstract structure of graphs

describe: be a property preserved under all possible isomorphisms of a graph

graph invariant: for properties expressed quantitatively

_eg: the number of vertices of degree 1 in a graph

property: descriptive characterizations(特性) of graphs

_eg: graph does not have vertices of degree 1 (is used to describe a class of graph)

a graph property is a class of graphs, with the property that any two isomorphic graphs either both belong to the class, or both do not belong to it

indicator function: test a graph is in the class of not. return true, if a graph in the class, return false, if it is not

** Properties of propertie

property classes

hereditary:

* Subgraphs

contains part of the graph, both vertex and adjacency relation(edge)

G's isomorphic is G's subgraph. G is G's subgraph?

G's spanning subgraph of factor: has same vertex set

induced subgraph:

H = (V1,E1), G = (V,E), H is subgraph of E,

all the edges between the vertices in V1 from E are in E1

(for all vertices in V1, if the two vertices have edge in E, the E1 much has an edge)

describe: if for any pair of vertices x and y of H,

_ xy is an edge of H if and only if xy is an edge of G

* source

百度百科 http://baike.baidu.com/view/79350.htm?fr=aladdin

Glossary of graph theory http://en.wikipedia.org/wiki/Induced_subgraph

Graph intro,has induce graph, and has example https://courses.cit.cornell.edu/info2950_2012sp/graph.pdf