Graphs defenitions Flashcards
What are the points called in graphs
Vertices or nodes
What are lines called in graphs
edges or arcs
what is order in graphs
its the number of edges going outwards from one node/vertex
what are 2 other ways to call ‘‘order’’
valency or degree
whats a walk
a walk is a route along edges from 1 vertex to another.
whats a path
a path is a walk in which no vertex/node is visited more than once.
whats a trail
a walk in which no edges are visited more than once
whats a cycle
a walk in which end vertex is the starting vertex and no other vertex visited more than once
whats a hamiltonian cycle
All vertices gone through once before returning exactly once before returning to starting vertex.
whats eulers handshaking lemma
sum of degrees of the vertices equals 2x number of edges
whats a tree graph
a tree is a connected graph with no cycles
whats spanning tree graph
a sub graph which includes all vertices and is a tree
whats a complete graph
every vertex is directly connected by a single edge to each of the other vertices
whats a simple graph
no loops, and max 1 edge connected 2 vertices
whats MST MINIMUM SPANNING TREE
a spanning tree with lowest sum of lengths
