Graphs And Networks Flashcards
What is a graph?
A graph consists of vertices/nodes which are connected by edges/arcs
What is a network/ weighted graph?
When graph has a number associated with each edge
What is a degree/valance/order of a vertex?
Number of edges connected to vertex/node
What is a path?
Sequence of edges. In which no vertex appears more than once
What is a walk?
A path in which you are permitted to return to vertices more than once
What is a cycle?
A closed path that forms a loop
What is a trail?
A walk where no arcs are repeated
What is a loop?
Starts and finishes at the same point
What is a simple graph?
No loops, not more than one edge connecting a pair of vertices
What is a Eulerian graph?
Each node has an even number of edges connected to it
What is a semi-eulerian graph
Graph that consists of 2 nodes with odd valency and the rest are even
What is a eulerian cycle?
Cycle that covers every arc
What is a eulerian graph?
No odd nodes
What is a Hamiltonian cycle?
Cycle that covers every node
What is a tree?
Connected graph with no cycles
What is a spanning tree?
Subgraph which includes all the vertices of a graph and is also a tree
What is a bipartite graph?
Consists of 2 sets of vertices. The edges only join vertices in C to vertices in Y
What is a complete graph?
Graph in which every vertex is directly connected by an edge to each other vertex.
What is a complete bipartite graph?
Graph in which there are r vertices in set X and s vertices in set Y (K s,r)
What is an isomorphic graph?
Shows the same info but drawn differently
What is a minimum spanning tree?
Connected graph with no cycles that includes all vertices. It also has the minimum weight
