graphs & networks

• verticies are adjacent is they are joined by an edge
• multiple edges: two or more edges connecting the same verticies
• a loop is an edge that joins a vertex to itself
• we must count the outside of a graph as a region (or face)
• isolated vertex: vertex that is not connected to any other vertex
• degree of a vertex is the number of edges going into a vertex (a loop is counted twice)
• degree sum = 2 x number of edges
• in degree = number of edges coming into that vertex
• out degree = number of edges going out of that vertex
• when listing vertex or edge sets use {}
• set of edges is given by {AB, AC, BC, BD}
• adjacency matrix: shows the number of edges joining each of the vertices in a graph
• simple graph: no loops or multiple edges
• connected graph: every vertex has an edge to at least on other vertex
• complete graph: a simple graph in which every vertex is joined to every other vertex by an edge
• subgraph: a graph is part of another graph
• a bridge: an edge in a connected graph that is removed leaves the graph disconnected
• bipartite graph: vertices can be split into two groups and edges join vertices from opposite groups
• planar graph: a graph that can be drawn in plane, no edges cross
• euler's fromula: V + F - E = 2
• walk: a route through a graph along edges
• length of a walk = number of edges it uses
• trail: a walk where no edges are repeated
• path: a walk where no edge or vertex is repeated
• closed trail = circuit
• closed path = cycle
• eulerian trail: a trail in a connected graph that travels each edge exactly once, you can repeat vertices but not edges
• eularian circuit: a closed eularian trrail
• eularian circuits begin and end at the same vertex
• eularian graph: a connected graph is considered to be eularian if it has an eularian circuit (have only even verticies)
• in a eularian graph the degree of each vertex will always be even
• semi-eularian trail: a eularian trail that starts and ends at different verticies
• semi-eularian graph: a connected graph is considered to be semi-eularian is it has a semi-eularian trail (has exactly two vertices that have odd degrees)
• hamiltonian path: travel through each vertex exactly once
• hamiltonian cycle: closed hamiltonian path
• semi-hamiltonian graph: travels through every vertex once but starts and finishes at different verticies