Graph representations & morphisms.html (2196B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" type="text/css" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.1.1 (456663)"/><meta name="keywords" content="ng"/><meta name="altitude" content="-0.7865003943443298"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-04-24 11:06:56 +0000"/><meta name="latitude" content="52.33454307835949"/><meta name="longitude" content="4.866740711664674"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-05-25 18:00:55 +0000"/><title>Graph representations & morphisms</title></head><body><div>Graph representation</div><ul><li><div>Adjacency matrix: symmetric. Rows and columns are nodes, cells contain number of edges between nodes</div></li><li><div>Incidence matrix: rows are vertices, columns are edges. Cell is 1 if the edge is incident on the vertex.</div></li><li><div>Subgraph: H is subgraph of G if V(H) ⊆ V(G) and E(H) ⊆ E(G) and ∀ (u,v) ∈ E(H) there is u,v ∈ V(H)</div></li><ul><li><div>in english: a subgraph of G has a subset of vertices and subset of edges of G</div></li></ul></ul><div><br/></div><div><b>Homomorphism</b> is a function ϕ: V(G1) ➝ V(G2) such that for each edge <u,v> ∈ E(G1) there is an edge <ϕ(u), ϕ(v)> ∈ E(G2)</div><div><br/></div><div><b>Isomorphism</b> is a <span style="font-style: italic;">one-to-one function</span> ϕ: V(G1) ➝ V(G2) such that for each edge <u,v> ∈ E(G1) there is an edge <ϕ(u), ϕ(v)> ∈ E(G2). it has to be unique, one-to-one.</div><ul><li><div>in english: two graphs have essentially the same elements with the same organisation. it’s a structure-preserving mapping.</div></li><li><div>Graphs are not isomorphic if:</div></li><ul><li><div>|V(G1)| ≠ |V(G2)|</div></li><li><div>|E(G1)| ≠ |E(G2)|</div></li><li><div>ordered degree sequence of G1 is different from ordered degree sequence of G2</div></li></ul></ul><div><br/></div></body></html>