maths.free › Combinatorics & Graph Theory › Graphs: vertices, edges, degrees
Graphs: vertices, edges, degrees
The basic objects of graph theory and the handshake lemma.
A graph is a set of vertices with edges between some pairs. The handshake lemma: the degrees sum to twice the number of edges, so the number of odd-degree vertices is even. Picture it: dots and lines; a complete graph on 5 vertices has 10 edges, which is 5 choose 2. Think it: graphs are relations drawn; the adjacency matrix makes them linear algebra.
Ejemplo resuelto · sum of k for k = 1 to 5
Paso a paso
- \sum_{k=1}^{5} k
Write the sum out.
- 1 + 2 + 3 + 4 + 5
Expand the terms.
- = 15
Closed form.
Revelar la respuesta
Ahora tú Escoge un problema, o escribe o dibuja el tuyo. Cada paso, una imagen, la respuesta oculta hasta que preguntes.
Una cuenta gratuita añade notas sobre cada lección, un registro de lo que has terminado, tus problemas resueltos en un lugar, y un tutor que puedes preguntar sobre esta página. Las matemáticas en sí están abiertas a todos, se han registrado o no.
Registrarse Inicio de sesiónSímbolos utilizados aquí
Toque cualquier símbolo para la definición completa, una imagen, y lo que cada letra en ella significa.
Cómo: Graphs: vertices, edges, degrees
- Write the sum out.
- Expand the terms.
- Closed form.
Preguntas que la gente hace
Permutation or combination?
Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).
What is a graph in this sense?
Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.
Más en Combinatorics & Graph Theory
The counting principlesPigeonhole principle and inclusion, exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsPaths, cycles, trees, Euler and HamiltonColouring and planar graphs