Graph Theory Vocab

what is Euler’s Rule and what graphs follow it?

V + F - E = 2. Followed by eulerian and semi-eulerian graph. Is the same as being traversable

Simple graph

has no multiple edges and/or loops

multiple edges

when two or more edges are connecting adjacent vertices

planar graph

all the edges must be drawn without crossing each other

complete graph

every vertex is connected to each of the other vertices. repesented with Kn

complete graph formula

E =[ n x (n-1)] / 2

degree of vertex in complete graph

n - 1

bridge

an edge which connects two parts of the graph together

weighted graph/ network

numbers that represent some quantiity that can be measured

semi-eulerian graph

needs to have exactly two odd vertices. must start at odd vertex and end up at other odd vertex (and follow euler’s rule)

eulerian graph

all vertices are even (and follow euler’s rule)

isolated vertex

a vertex that is not connected to the graph

multiple edges

when two or more edges connect adjacent vertices

subgraph

all vertices chosen must be connected. note the original graph is a subgraph of itself.

bipartite graph

Vertices must be separated into two distinctive categories and adjacent vertices must not be gained

walk

any route through a graph from vertex to vertex along the connecting edges

graph

any diagram that consists of nodes/vertices and edges/arcs

regular graph

all vertices have the same degree

what powers of adjacency matrix represent:

no power - eg. if A to B is 1, there is a walk of length 1 connecting A and B

squared -eg. 2 walks of length 2 connecting A to itself with one stopover

what does N= M + M² represent

This shows total number of walks with at most 1 stop over and 2 stop overs.

hamiltonian graph

starts and finishes at same vertex and includes every other vertex only once