Graphs

Questão	Responda
Graph	A finite set of points connected by lines
Edge	Joins one vertex to another, or starts and ends at the same vertex (a loop)
Simple	No loops or multiple edges
Connected	Every vertex is connected by a single edge or sequence of edges to every other vertex
Disconnected	Can be separated into two separate 'pieces'
Complete	Every vertex is connected to every other vertex by one edge -- Denoted K
Subgraph	Part of a graph which is itself a graph
Planar	A graph which can be drawn without any edges crossing over
Degree (Vertex)	The number of edges which start or finish at a vertex (count loops twice)
Handshaking Theorem	Σ(degrees of vertices) = 2 (number of edges)
Digraph	A graph whose edges have a direction
Bipartite	A graph with two discrete sets of vertices, with no edges connective vertices in the same set
Complete Bipartite	A bipartite graph in which every vertex in one set is connected to every vertex in the other set by one edge -- Denoted K
Isomorphic	Identical graphs which have been drawn in different orientations
Walk	A sequence of edges and vertices in which the end of one edge is the beginning of the next
Trail	A walk with no repeated edges (in either direction)
Path	A walk with no repeated vertices (except that the first may be the last)
Cycle	A closed walk, trail or path -- Finishes at the same vertex where it started
Eulerian Trail	Crosses every edge of a graph exactly once -- Has no vertices with an odd degree
Semi-Eulerian	Has only two odd vertices; only transversible if you start and finish at the odd vertices
Hamiltonian Cycle	A closed path which passes through every vertex of a graph
Tree	A connected graph which contains no cycles
Spanning Tree	A subgraph which includes all vertices of the original graph, and is also a tree

Próximo

Descrição

Resumo de Recurso

Semelhante

	Criado por Nathanael Jenkins aproximadamente 5 anos atrás