Fichas
Graph Theory
Fichas del conjunto (21)
- 1What does a graph consist of?Vertices (nodes)
Edges (arcs) - 2What is the degree (order) of a vertex?Number of edges connected to a vertex
- 3What is a network (weighted graph)?Graph with numbers linked to each edge
- 4What is a connected graph?Where it is possible to travel from any vertex to any other vertex (perhaps passing through other vertices on the way)
- 5What is a loop?Edge whose beginning and edge are the same vertex
- 6What is a simple graph?No loops or repeated edges
- 7What is a digraph (direct graph)?Directed edges
- 8What is a 'Complete Graph Kn'?Graph has vertices with each vertex joined to every other vertex and has
n(n-1)/2 edges - 9What is a bipartite graph?Graph has 2 sets of vertices and edges only connect to vertices from one set to the other
- 10What is a trail?A sequence of edges that only include edges at least once
- 11What is a tour?Ends and starts at the same vertex
- 12What is a path?A trail where no vertex is visited more than once (except start/finish)
- 13What is a cycle?A closed path
- 14What's a Hamiltonian cycle?A cycle that visits every vertex
- 15How many Hamiltonian cycles does a compete graph with n vertices have?(n-1)/2 Hamiltonian cycles
- 16What is a Eulerian trail?Uses every edge. The degree of each vertex must be even
- 17What's a semi-Eulerian graph?A non-closed trail that uses all edges. All vertices except 1 will be even
- 18What is a tree?A connected graph with no cycles or repeated edges
- 19What is a spanning tree?A simple connected graph with fewer edges than vertices
- 20What is a minimum spanning tree?A spanning tree with a minimum weight
- 21What can a graph be represented by?Adjacency matrix
Información
- Descripción
- AS level Maths AS Fichas sobre Graph Theory, creado por Alice Hathaway el 19/02/2017.
- Creado por
- Alice Hathaway
- Visitas
- 0
- Valoración
Más sobre Graph Terminology and Types