Ayúdanos a dar forma a GoConqr. ¿Qué deberíamos añadir?

Apuntes

Summary of Chapter 2

jakubburger Decision Inglés 1 página

Contenido del apunte (1)

Página 1

1 A graph consists of

vertices(nodes) which are connected by edges(arcs).

2 A subgraph is part

of a graph.

3 If a graph has a

number associated with each edge (its weight) then the graph is a weighted

graph (network).

4 The degree or

valency (or order) of a vertex is the number of edges incident to it.

5 A path is a finite

sequence of edges, such that the end vertex of one edge in the sequence is the

start vertex of the next, and in which no vertex appears more than once.

6 A walk is a path in

which you are permitted to return to vertices more than once.

7 A cycle (circuit)

is a closed ‘path’, i.e. the end vertex of the last edge is the start vertex of

the first edge.

8 Two vertices are

connected if there is a path between them. A graph is connected if all its

vertices are connected.

9 A loop is an edge

that starts and finishes at the same vertex.

10 A simple graph is

one which there are no loops and not more than one edge connecting any pair of

vertices

11 If the edges of a

graph have a direction associated with them they are known as a directed edges

and the graph is known as a digraph.

12 A tree is a

connected graph with no cycles.

13 A spanning tree of

a graph, G, is a subgraph which includes all the vertices of G and is also a

tree.

14 A bipartite graph

consists of two sets of vertices, X and Y. The edges only join vertices in X to

vertices in Y, not vertices within a set.

15 A complete graph

is a graph in which every vertex is directly connected by an edge to each of

the other vertices. If the graph has n

vertices the connected graph is denoted kn.

16 A complete

bipartite graph (denoted kr,s) is a

graph in which there are r vertices

in set X and s vertices in set Y.

17 Isomorphic graphs

show the same information but are drawn differently.

18 An adjacency

matrix records the number of direct links between vertices.

19 A distance matrix

records the weights on the edges. Where there is no weight, this is indicated

by ‘-‘.

Page 1

Información

Descripción
(Chapter 2: Graphs and networks) Decision Apunte sobre Summary of Chapter 2, creado por jakubburger el 11/04/2013.
Creado por
jakubburger · abr 2013
Actualizado
16 ago 2016
Visitas
96
Etiquetas
chapter 2: graphs and networksdecision
Valoración

Más sobre Graph Terminology and Types

Escríbenos

¿Sobre qué es tu mensaje?

¿Qué deberíamos añadir?