Components of a Graph (27/07/2021)

A graph, in mathematics, does not refer to the graphs of functions that you are shown in high school. Informally, a graph is a collection of points connected by lines. The way you would write this mathematically is G=(V, E), where V is the collection of points or vertices and E is the collection of lines or edges.

Def. A walk is a sequence of incident vertices and edges in a graph.

Def. A path is a walk with no repeating vertices.

Def. Two vertices are connected if there is a path in the graph that has them as endpoints.

Def. A component of a graph G is a connected subgraph of G that is not a proper subgraph of any other connected subgraph in G.

The above definition is a bit hard to swallow, but it means just what you would think; components are pieces of a graph.

I noticed something peculiar; let G_1 be the number of vertices, G_2 the number of edges, G_3 be the number of faces, etc, then the following is true:

Conjecture. The number of components in a simple graph is given by the alternating sum of G_i.

Comments

Post a Comment

Popular posts from this blog

Introduction (25/07/2021)

My name is Vimal Vinod, and I am 17 years old. The recent video by  3Blue1Brown  " Why aren't you making your own math videos? " convinced me to start this maths blog. So, what kind of maths will I be talking about? All sorts; Analysis, Linear Algebra, Abstract Algebra, Number Theory and stuff from Discrete Maths like Combinatorics and Graph Theory. Mostly I will be writing about what I am learning, the resources I used, and sometimes I may try to write maths explanations. I hope you find this blog useful!
Read more

Summer Reading (17/07/2021)

Have recently begun reading maths textbooks. The aim is to build a solid foundation in the subjects taught at undergrad. My initial aim is to read the books recommended by  The Math Sorcerer . Some books I have liked so far include: Introduction to Analytic Number Theory  by Tom M. Apostol All the Mathematics You Missed  by Thomas A. Garrity Linear Algebra and its Applications by Gilbert Strang Analysis I by Terrance Tao Leonard Susskind 's Theoretical Minimum Series are books on applied maths; they teach you the maths behind physics. Books by Ian Stewart,  like The Great Mathematical Problems , might also be worth a read.
Read more

Computer Vision (31/07/2021)

Image
Computer vision aims to extract information from the surroundings using cameras. This is much harder than you might think - think about how you might tell a computer how to recognise an elephant for example: Happy the elephant at Bronx Zoo You couldn't just say that it is grey, has four legs and a trunk. The computer probably doesn't know what an animal even is or what any of those words mean. Sure it might be easy to program it to look for grey pixels, but then it might mistake a rock for an elephant. And what if the camera is positioned in a way that makes it difficult to distinguish the different legs, or if the trunk wasn't visible? I have been interested in computer vision for quite a while now but had no idea where to start. Recently, I got this book  Concise Computer Vision: An Introduction Into Theory and Algorithms . It's got good reviews, but I had trouble implementing the stuff from the first few chapters. A better resource for beginners might be MIT's In...
Read more