Fichas
Basic Terminology
Fichas del conjunto (32)
- 1Here is an example graph:
- 2What is a vertex?A point of the graph (e.g. A,B,C,D,E)
(aka nodes) - 3What is an edge?Line between vertices (e.g. A-E)
- 4What is a walk?Sequence of linked vertices (e.g. A-B-C-B)
- 5What is a trail?A walk without any repeated edges (e.g. A-B-C-E-A) note vertices can be repeated, just no edges
- 6What is a path?A walk without any repeated edges or vertices (e.g. A-B-C-D)
- 7What is a cycle?A path which starts and ends in the same place (e.g. A-B-C-D-E-A)
- 8What is a closed path, trail or walk?Starts and ends at the same vertex (cycle)
- 9What is an open path, trail or walk?Doesn't start and end at the same vertex
- 10What is a connected graph?When you can get from any vertex to any other other vertex (e.g. A->D is A-E-D)
- 11What is multiple edge?If there is more than 1 edge between 2 vertices
- 12What is a loop?If an edge has the same start and end vertex
- 13What is a simple graph?If the graph has no loops or multiple edges
- 14What is a tree?A simple graph with no cycles
- 15What is a subgraph?Any graph that can be formed using some of the vertices and some of the edges from the original graph
- 16What is a subdivision?When you delete an edge from graph and replace it with another edge that has a vertex in the middle of it (must include all original edges)
(Basically adding vertex between 2 edges) - 17What is a complete graph?A simple graph that has every vertex connected to every other vertex (represented by Kn)
- 18Draw K1 to K6
- 19What formula can determine the amount of edges for Kn?1/2 n(n-1)
- 20What is the complement of a graph?It has edges that are need to be added to the original graph to make it complete
- 21What is a bipartite graph?A graph which links 2 independent groups of vertices
- 22What is a complete bipartite graph?Links every vertex in group M to every vertex in group N
- 23What is the notation for a complete bipartite graph?Km,n
M=group 1, N=group 2 - 24For Km,n how many vertices and how many edges does it have?Vertices = m+n
Edges = mn - 25What does the word isomorphic mean?When graphs are the same but just drawn / look differently
- 26What is an adjacency matrix?A way to represent a graph in table form
- 27What do the numbers in the adjacency matrix represent?The number of edges (between the 2 vertices)
- 28A loop accounts for how many edges in a adjacency matrix?2
- 29What is the order / degree of a vertexthe number of edges meeting at that vertex (remember loops count as 2 edges)
- 30Example of adjacency matrix:
- 31How many edges does a tree with n vertices have?n-1
- 32If asked to find a rule which we don't know for that specific circumstance, what should we do to help us?Draw it a few times to check it works