이언배 연구노트

네이버 API 검색이 끝났다. import pandas as pdfrom sqlalchemy import create_enginefrom glob import globfilenames = glob('./api_crawl_1/*.csv')dfs = []for file in filenames: t = pd.read_csv(file) dfs.append(t)filenames = glob('./api_crawl_2/*.csv')for file in filenames: t = pd.read_csv(file) dfs.append(t)df_concat = pd.concat(dfs)engine = create_engine('postgresql+psycopg2://???:???@???:5432/??..

그래프를 종이에 그릴 수 있겠니? 선이 겹치면 헷갈리잖아. 규칙을 몇 개 정해줄게. DefinitionDrawing a multigraph두 edge 를 crossing: 공통의 internal point 가진다는 것emdgedding: crossing 이 없는 drawingplanar: multigraph 가 plane 에 embed 가능plane multigraph: multigraph 를 planar embedding 하게 그린 예시"안겹치게 잘 그려봐" Proposition$K_5$ 랑 $K_{3, 3}$ 은 planar 그래프가 아니다.5개짜리 complete graph 랑 3대3 complete bigraph 는 안겹치고는 못 그린다.$\textit{Proof}$$C$ 라는 spanning c..

job assignment problem 을 생각해보자.총 n 개의 job 이 있고, set $A$ 만큼의 지원자가 있다고 하자.$A$ 중에서 $A_i$ 가 $i$ 번째 직종에 지원 가능하다고 했을 때, $A_1$ 부터 $A_n$ 까지 각각 한명씩 매칭시킨 $x_1$ 부터 $x_n$ 을 찾을 수 있다.이게 대표적인 system of distinct representatives 문제. Definition.A matching: a set of pairwise non-incident edges (independent edges): vertex가 안겹치는 edge 들의 set.matching covers the vertices: matching 에 포함되는 edge 들에 닿은 vertex 들.perfect m..

NAVER web crawling 결과로 도무지 파악할 수 없었던 인허가 데이터를NAVER API 를 활용해 하나하나 쿼리해본 결과를 csv로 저장해뒀다. 이제 이 결과물을 PostGRES 로 옮겨서 SQL로 다시 한 번 매칭해볼 것이다. 폴더에 저장된 csv 들을 불러들여 PostGRES로 이동시키는 건 간단하다. import pandas as pdfrom sqlalchemy import create_engine #Dataframe -> SQL 에는 sqlalchemy 를 불러오자from glob import glob# csv 파일들 불러오기filenames = glob('./폴더이름이뭐에요/*.csv') #glob 함수에서 '*.csv' 는 모든 csv 파일을 불러준다. 이 결과물은 'text의 리스..

6.4. List coloring and Brooks' TheoremDefinitionlist assignment (L): a function on $V(G)$ such that $L(v)$ 가 $v$에게 'acceptable' 한 색상 set이다. $v$ 가 가질 수 있는 색상의 리스트 매핑L-coloring: $f(v) \in L(v)$ for all $v$. 모든 $v$ 가 가질 수 있는 색상 리스트 L 내에서 적절히 골라갈 수 있다.k-choosable : L-coloring whenever $|L(v)| \geq k$ for all $v$. 색상 리스트가 모두 $k$개 이상인 상태에서 L-coloring 이 가능.list chromatic number / choice number / choosa..

Definitionwalk: sequence $v_1v_2...v_k$  of vertices and a sequence of edges $v_iv_{i+1} \in E(G)$. edge 로 건너건너Closed walk: $v_1 =v+k$. 어찌되었건 건너건너 돌아옴trail: all edges are distinct. Edge 안겹치고 건너건너closed trail: Edge 안겹치고 건너건너 돌아옴path: all vertices are distinct. Vertex 안겹치고 건너건너Cycle: closed walk 인데 vertex 안겹치고 건너건너 돌아옴.Length of the walk: k-1 G is connected: all pairs $u, v \in V(G)$, there is a p..

Definition.Graph G: a pair (V, E)V(G): a set of verticesE(G): a multiset of edges$|G| = |V(G)|$: the order of G: order 은 vertex 갯수$e(G) = |E(G)|$: the size of G: size 는 edge 갯수Loop: an edge of size 1graph 가 simple 하다: loop 나 multiple edge가 없다 u 와 v 가 adjacent: $uv \in E(G)$. 둘 사이 edge가 있다v 와 e가 incident: $v \in e$, edge 중 하나에 포함된다e 와 e'가 incident: $e \cap e' \neq \emptyset$ e랑 e' 는 공통의 vertex를 가..

Edge present 'conflict'6.1 Chromatic number and bounds on itDefinitionk-coloring: vertex labeling $f: V(G) \rightarrow S$ where $|S| = k$. 각 vertex마다 k개 중에 하나로 labelingk-coloring f is proper: $f(x) \neq f(y)$ when $xy \in E(G)$. 붙어있는 애들끼리는 다른 색으로 labelling하는 fk-colorable: proper k-coloring 이 있음The chromatic number $\chi(G)$: minimum k such that G is k-colorable. proper coloring 가능하게 만드는 최소 색상 갯수..