Networks Flashcards
Edges
The sets of lines that join vertices
Vertices
A set of points
Loop
An edge that starts and ends at the same vertex
Multiple edges
When two or more edges connect the same two vertices
Adjacent vertices
When two vertices are connected by a path that only involves one edge
Degree of vertex
The number of edges connecting to the vertex
Sum of degrees
Formula that says if you add up of the degrees of the vertices in a graph, the result is twice the number of edges in the graph
Isolated vertice
A vertice that is not connected to any other vertices. It has a degree of 0
Null graph
A graph made up of multiple isolated vertice, has no edges
Regular graph
A graph in which each vertice has the same number of degrees
Weighted graph
Graphs that have amounts, distances or some information on each edge
Subgraph
A portion of an existing graph
Trivial graph
A graph containing one single isolated vertice
Simple graph
An undirected, unweighted graph with no loops or multiple edges
Connected graph
A graph where every vertex is connected to every other vertex. (Meaning travelling across several edges is applicable)
Complete graph
Simple graphs in which every vertice is connected to every other vertice by, in each case, a single edge
Planar graph
A graph where no edges cross over each other
Euler’s formula
vertices-edges+faces=2
If a graph doesnt fit euler’s formula?
There is not a connected, planar network with those properties
What statement defines a connected planar graph?
Connected planar graphs have an even number of vertices with odd degrees
Bipartite graph
A graph whose vertices can be divided into 2 groups such that each edge connects a vertex from one group to a vertex in another. Vertices in a group are never connected to other vertices in that group
Matrix properties
- A loop is counted as one edge
- The sum of the row entries gives the degree of the vertex corresponding to that row. For any vertex containing a loop, 1 must be added as a loop is counted as two edges in the context of the degree of a vertice
Eulerian graph
It has a closed trail (Starts and finishes at same vertices) that includes every edge once only. The graph must be connected and have all vertices of an even degree
Semi-eulerian
It has an open trail (Starts and finishes at different vertices) that includes every edge once only. The graph must be connected and have two vertices of an odd degree
Where do semi-eulerian trails start and finish
Must start at one of the odd vertices and finish at another
Hamiltonian cycle vs path
Path: Goes to every vertex
Cycle: Goes to every vertex and starts and ends at the same vertex
