the Flow De-composition Theorem:
Obtain a max-flow and consider the residual graph
27 Matching Annotations
- Apr 2025
-
-
-
An alternative proof
My Proof: Based on conservation law, split the network into s, L, R, t with nflow(L) = nflow(R) = 0, nflow(s) = excessive(t) for any split, thus max-flow <= min-cut.
Given a max-flow, remove an edge and reducing flow value from all down-stream flowing edge repetitively. Eventually total flow value of removed edge must = nflow(s) and it must be a cut (otherwise the original flow can be arugmented and not maximized).
-
Lemma 8.3. For any A ⊆ V (G) such that s ∈ A, t /∈ A, and any s-t-flow f ,(a) value ( f ) = ∑e∈δ+( A) f (e) − ∑e∈δ−( A) f (e).(b) value ( f ) ≤ ∑e∈δ+( A) u(e)
Better Proof: The (net) outflow of a set of vertice equal the sum of net flow of each vertice (Just write the forumla) and is thus equal to zero due to conservation law. So nflow(A, s) + nflow(A, V \ A \ s) = 0 the former is = - nflow(s).
-
- Nov 2024
-
www.zylstra.org www.zylstra.org
-
How to Spot Emerging Note Clusters Without Alphanumeric Note Numbering? by [[Ton Zijlstra]] in Interdependent Thoughts
I recall Bob Doto had a video at some point in which he used the local graph to show relationships to find bunches of notes for potentially writing pieces or articles as indicated in Tons' article.
One of the biggest issues with digital note taking tools is that they don't make it easy to see and identify chains of notes which might make for articles, chapters, or books.
Surely there must be some way to calculate neighborhoods of notes from a topological perspective? Perhaps if one imposed a measure on the space to create relative distances of notes?
-
- Feb 2023
-
forum.zettelkasten.de forum.zettelkasten.de
-
fz is less about the tree (though that is important) and more about the UX.
I do like the framing of folgezettel as a benefit with respect to user experience.
There is a lot of mention of the idea of trees within the note taking and zettelkasten space, but we really ought to be looking more closely at other living systems models like rhizomes and things which have a network-like structure.
-
- Jan 2022
-
www.youtube.com www.youtube.com
-
https://www.youtube.com/watch?v=z3Tvjf0buc8
graph thinking
- intuitive
- speed, agility
- adaptability
; graph thinking : focuses on relationships to turn data into information and uses patterns to find meaning
property graph data model
- relationships (connectors with verbs which can have properties)
- nodes (have names and can have properties)
Examples:
- Purchase recommendations for products in real time
- Fraud detection
Use for dependency analysis
-
- Mar 2021
-
en.wikipedia.org en.wikipedia.org
-
graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects
-
-
-
Devriendt, K., Martin-Gutierrez, S., & Lambiotte, R. (2020). Variance and covariance of distributions on graphs. ArXiv:2008.09155 [Physics, Stat]. http://arxiv.org/abs/2008.09155
-
- Sep 2020
-
www.springer.com www.springer.com
-
Kiss, I. Z., Miller, J., & Simon, P. L. (2017). Mathematics of Epidemics on Networks: From Exact to Approximate Models. Springer International Publishing. https://doi.org/10.1007/978-3-319-50806-1
-
- Aug 2020
-
panopto.lshtm.ac.uk panopto.lshtm.ac.uk
-
CSM_seminar Causal Inference Isn't What You Think It Is. (2020). Retrieved 24 August 2020, from https://panopto.lshtm.ac.uk/Panopto/Pages/Viewer.aspx?id=ac88b49f-7e63-458d-823e-abe50152fb66
-
-
en.wikipedia.org en.wikipedia.org
-
In graph theory, a tree is a connected acyclic graph; unless stated otherwise, in graph theory trees and graphs are assumed undirected. There is no one-to-one correspondence between such trees and trees as data structure.
-
- Jun 2020
-
www.lshtm.ac.uk www.lshtm.ac.uk
-
Causal inference isn’t what you think it is. (n.d.). LSHTM. Retrieved June 26, 2020, from https://www.lshtm.ac.uk/newsevents/events/causal-inference-isnt-what-you-think-it
-
- May 2020
-
psyarxiv.com psyarxiv.com
-
Blanchard, M. A., & Heeren, A. (2020). Why We Should Move from Reductionism and Embrace a Network Approach to Parental Burnout? [Preprint]. PsyArXiv. https://doi.org/10.31234/osf.io/y34cq
-
-
en.wikipedia.org en.wikipedia.org
-
This is an abstract form of De Morgan's laws, or of duality applied to lattices.
-
-
en.wikipedia.org en.wikipedia.org
-
A plane graph is said to be self-dual if it is isomorphic to its dual graph.
-
-
-
en.wikipedia.org en.wikipedia.org
-
en.wikipedia.org en.wikipedia.org
Tags
Annotators
URL
-
- Apr 2020
-
en.wikipedia.org en.wikipedia.org
-
Equivalently, an arborescence is a directed, rooted tree in which all edges point away from the root
-
-
www.w3.org www.w3.org
-
This graph view is the easiest possible mental model for RDF and is often used in easy-to-understand visual explanations
Tags
Annotators
URL
-
- Dec 2019
-
github.com github.com
-
arborescence
First sighting of word arborescence. I thought they were just doing that for fun, as a play on "tree", but I guess it's a real graph theory concept (https://en.wikipedia.org/wiki/Arborescence_(graph_theory)).
Tags
Annotators
URL
-
-
en.wikipedia.org en.wikipedia.org
-
branching
I like this as a good alternative to the word arborescence. It seems to intuitively describe the concept using a more English-sounding word: it's talking about a specific branch/branching of the tree. Right?
-
- Dec 2018
-
mrpandey.github.io mrpandey.github.io
- Apr 2017
-
waitbutwhy.com waitbutwhy.com
-
Two people can have one conversation. Three people have four unique conversation groups (three different two-person conversations and a fourth conversation between all three as a group). Five people have 26. Twenty people have 1,048,554.
what's the equation for that?
-
- Sep 2016
-
en.wikipedia.org en.wikipedia.org
-
A forest is just a collection of trees. The main difference is that a forest does not necessarily need to be connected.
-